1-D Dynamic Programming

### Giai đoạn: Nền Tảng & Khái Niệm Cốt Lõi **1-D Dynamic Programming** Dynamic programming is the technique of breaking a problem into overlapping subproblems, solving each once, and storing the result to avoid recomputation. In one-dimensional DP, each state depends only on a fixed number of previous states, so the solution builds a single array from left to right. The first step is always identifying the recurrence: what does the answer at position i depend on? The problems here cover the core DP patterns you will see repeatedly: linear sequences, knapsack decisions, and string segmentation. DP problems are notoriously hard to recognize, and the only reliable way to get better at them is to solve many and study the structure of their recurrences. ### Khái niệm cốt lõi: 1. **The first step is always identifying the recurrence: what does the answer at position i depend on** ### Tài liệu tham khảo chính thống: - [1-D Dynamic Programming Problem](https://www.scaler.com/topics/data-structures/1-d-dynamic-programming-problem/) (article) - [5 Simple Steps for Solving Dynamic Programming Problems](https://www.youtube.com/watch?v=aPQY__2H3tE) (video)