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.