DSA: Dynamic Programming
Learn to solve complex problems by breaking them into overlapping subproblems and caching results.
What is Dynamic Programming?
Dynamic Programming (DP) is an optimization technique that solves problems by breaking them into smaller subproblems, solving each subproblem once, and storing the result to avoid redundant computation.
Dynamic Programming
Applicable when a problem has two key properties: overlapping subproblems and optimal substructure.
- Overlapping subproblems: the same subproblem is solved multiple times in naive recursion
- Optimal substructure: optimal solution builds on optimal solutions of subproblems
- Two approaches: memoization (top-down) and tabulation (bottom-up)
- Transforms exponential time to polynomial time in many problems
Naive Recursion
C++Exponential time due to repeated subproblem computation.
Memoization (Top-Down)
Memoization stores the result of each subproblem in a cache (usually a map or array) the first time it is computed. Subsequent calls return the cached value instantly.
Memoization
Top-down DP: write the recursive solution, then add a cache to skip repeated work.
- Cache: typically an array or unordered_map indexed by subproblem state
- Time complexity: O(n) for Fibonacci instead of O(2^n)
- Space complexity: O(n) for the cache plus O(n) call stack
- Easy to implement: start from recursive solution, add memo table
Fibonacci with Memoization
C++Cache results to avoid redundant recursive calls.
Tabulation (Bottom-Up)
Tabulation fills a DP table iteratively, starting from the smallest subproblems and building up to the final answer. No recursion stack is used.
Tabulation
Bottom-up DP: fill a table from base cases up to the target, no call stack overhead.
- Iterative: uses a for-loop instead of recursion
- Space optimizable: many problems only need the last 1 or 2 values
- Avoids stack overflow risk present in deep memoization recursion
- Usually preferred in competitive programming for speed
Fibonacci with Tabulation
C++Fill the dp array from base cases iteratively.
Climbing Stairs
Count the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. This is structurally identical to Fibonacci.
Climbing Stairs
dp[i] = number of ways to reach step i. Recurrence: dp[i] = dp[i-1] + dp[i-2].
- Base cases: dp[1] = 1, dp[2] = 2
- At each step you arrived from i-1 (1 step) or i-2 (2 steps)
- Same recurrence as Fibonacci shifted by one index
- Space-optimized with two variables instead of full array
Climbing Stairs
C++Space-optimized O(1) solution using two variables.
House Robber Problem
Given an array of house values, find the maximum amount you can rob without robbing two adjacent houses.
House Robber
At each house choose: rob it (add to dp[i-2]) or skip it (keep dp[i-1]).
- Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- dp[i-1]: best without current house
- dp[i-2] + nums[i]: best skipping previous, robbing current
- Space-optimized to O(1) using two variables
House Robber
C++Maximum loot without robbing adjacent houses.
Maximum Sum of Non-Adjacent Elements
A generalization of House Robber: find the maximum sum of elements from an array such that no two selected elements are adjacent.
Non-Adjacent Sum
Identical recurrence to House Robber. Build understanding before tackling 2D DP variants.
- Same as House Robber with generic integer input
- Works for any 1D array where adjacent selections are forbidden
- Builds intuition for the include/exclude DP pattern
- Include/exclude pattern: for each element decide to take it or not
Maximum Non-Adjacent Sum
C++Include/exclude pattern: pick elements no two of which are adjacent.
Minimum Cost Climbing Stairs
Each stair has a cost. You can start at index 0 or 1, and from each step you can move 1 or 2 steps. Find the minimum cost to reach the top (past the last index).
Min Cost Climbing Stairs
dp[i] = min cost to reach step i. Answer is min(dp[n-1], dp[n-2]).
- Recurrence: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
- Base cases: dp[0] = cost[0], dp[1] = cost[1]
- Top of staircase is index n, reached from n-1 or n-2
- Answer: min(dp[n-1], dp[n-2]) since you pay on departure
Minimum Cost Climbing Stairs
C++Find cheapest path to the top paying cost on each step taken.
Memoization vs Tabulation
Both approaches produce the same result. Choose based on problem constraints and personal preference.
| Property | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Approach | Recursive + cache | Iterative table fill |
| Ease of implementation | Easier: modify existing recursion | Requires knowing fill order |
| Stack usage | O(n) call stack | O(1) no call stack |
| Computes only needed states? | Yes: lazy evaluation | No: fills all states |
| Risk | Stack overflow on large n | None |
| Speed in practice | Slightly slower (function call overhead) | Slightly faster |
Knowledge Check
1. What is the key property that makes a problem suitable for Dynamic Programming?
2. What is memoization?
3. What is the time complexity of Fibonacci using memoization vs naive recursion?
4. In the Climbing Stairs problem, how many ways can you climb n stairs (1 or 2 steps at a time)?
5. What constraint does the House Robber problem enforce?
6. Which approach builds the DP solution from the smallest subproblems up?
7. What is the base case for the Fibonacci DP table?