1D Dynamic Programming
Dynamic programming solves optimization or counting problems by splitting them into overlapping subproblems and saving the results so nothing is computed twice. "One-dimensional" means the state needs only a single index i, stored in one dp array.
Two conditions make it applicable: subproblems repeat many times, and the big solution can be assembled from the small ones. Finding the right transition formula is the hardest part; many problems only need the last few values, so memory can be optimized down to O(1).
Like a spending ledger — once you've worked something out, write it down and just look it up next time.
- It avoids recomputing subproblems you've already solved: store the results of small subproblems and combine them into the answer for the bigger one.
- Each cell in the dp table is a "known answer".
How to spot it
When you see these cues in the problem, reach for 1D Dynamic Programming
| Keyword in the problem | Why it points to this topic |
|---|---|
| count the ways | Counting problems are usually DP |
| min / max at step i | Classic optimisation DP |
| climbing stairs / partition | Recursive structure with discrete choices |
| TLE on naive recursion | Add memoisation or tabulation |
When to use
3 typical situations where this topic applies
The problem has a recursive structure with overlapping subproblems
You need to optimize a max / min, or count the number of ways to do something
The problem has a "choice" at each step: take or skip, climb a step or not
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
The state has several dependent dimensions (position + balance + remaining): you need 2D/3D DP, not 1D
A greedy local-optimal choice is enough: DP is overkill, greedy is shorter
Subproblems do not repeat (no overlap): it is not DP — it is plain divide & conquer / recursion
Illustration
A diagram of how this topic works.
Each cell stores the result of one subproblem. Compute left to right — each cell builds on earlier ones, nothing is recomputed.
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function dp1d(n: number, /* params */): R {
const dp = new Array(n + 1).fill(initValue)
dp[0] = baseCase0 // base case
// dp[1] = baseCase1 // if needed
for (let i = 1; i <= n; i++) {
dp[i] = transition(dp[i - 1], dp[i - 2], /* ... */)
}
return dp[n]
}
// O(1) space variant when only the last two states matter:
function dp1dOptimized(n: number): R {
let prev2 = baseCase0
let prev1 = baseCase1
for (let i = 2; i <= n; i++) {
const curr = transition(prev1, prev2)
prev2 = prev1
prev1 = curr
}
return prev1
}Recap
A quick summary — reread it before your interview
Key points
Define the subproblem: what is dp[i]? What does the index i mean?
Write the recurrence from smaller subproblems to larger ones
Tabulation (bottom-up) uses less stack than memoization (top-down)
Many 1D DP problems can cut space from O(n) to O(1) by keeping only the previous 1–2 values
Common mistakes
Wrong base cases (dp[0], dp[1]) → the answer is wrong from the start
Wrong loop direction (forward or backward?) when optimizing space
Mistaking a problem that needs 2D DP (matrix, substring) for a 1D one
Complexity
Time O(n), Space O(n) hoặc O(1) tuỳ bàiPractice problems for this topic
Grouped by difficulty — work through them in order to build confidence