Stage 1 · Code
Dynamic Programming & Greedy
1D Dynamic Programming
State, recurrence, base case — the three pillars of DP. Solve any linear sequence problem by defining dp[i] in terms of dp[i-1] or earlier.
The Pattern
1D DP is the entry point to dynamic programming. The idea: solve the problem for all prefixes of size 0..n, where each answer dp[i] is computed from earlier dp values. This turns exponential recursion into O(n) computation by caching repeated subproblems.
Every DP solution needs three things: a state (what does dp[i] represent?), a recurrence (how to compute dp[i] from smaller i?), and base case(s). Once you have these, the code practically writes itself.
Draw the recursion tree for fib(5). Notice fib(3) appears twice? That's overlapping subproblems. When you memoize, the tree collapses to a line — O(2ⁿ) → O(n).
State Design
The most common 1D states:
- dp[i] = best value for prefix of size i (Climbing Stairs, House Robber).
- dp[i] = length of something ending at i (Longest Increasing Subsequence).
- dp[i] = true/false if sum i is achievable (subset sum / knapsack variants).
Bottom-Up vs Top-Down
When to Use
- Linear sequence: Fibonacci, climbing stairs, decoding ways.
- Decision at each step: house robber, best time to buy/sell stock with cooldown.
- Subsequence problems: LIS, longest palindromic substring.
- The problem asks for 'minimum/maximum number of ways' or 'minimum cost'.
- Brute-force is exponential and you notice repeated subproblems — draw the tree.
Problems
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.