1D Dynamic Programming

One-dimensional DP compresses a decision history into a single index or amount. The central question is: what does dp[i] mean, and which earlier states can legally transition into it?

Mental Model

• Index DP: answer for prefix ending at i.
• Amount DP: answer for target value i, common in coin and subset-style problems.
• Choice split: take/skip, extend/reset, decode one/two characters, rob/skip.
• Optimization: keep only the previous few states when the recurrence does not need the whole table.

Diagram

Problem List

Start with 070. Climbing Stairs, 198. House Robber, 322. Coin Change, 300. Longest Increasing Subsequence, and 416. Partition Equal Subset Sum.