curriculum/challenges/english/blocks/lecture-understanding-dynamic-programming-js/699951f2b5e66fca32749fb2.md
Dynamic programming is an algorithmic technique that solves complex problems by breaking them down into simpler subproblems and storing the results to avoid redundant calculations. This approach transforms problems that would normally take exponential time into ones that can be solved in polynomial time.
Dynamic programming works when two key conditions are present in a problem.
Overlapping Subproblems: The same smaller problems appear multiple times when solving the larger problem. Instead of recalculating these subproblems repeatedly, we store their solutions.
Optimal Substructure: The optimal solution to the problem contains optimal solutions to its subproblems. This means we can build up the best solution by combining the best solutions to smaller parts.
Let's examine these concepts using the classic "climbing stairs" problem.
Consider the climbing stairs problem: you're climbing a staircase with n steps and can climb either 1 or 2 steps at a time. How many distinct ways can you reach the top?
function climbStairsRecursive(n) {
// Base cases: 1 way for 1 step, 2 ways for 2 steps
if (n <= 2) {
return n;
}
// Recursive rule: to reach step n, you can come from step (n-1) or step (n-2)
return climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2);
}
This implementation has exponential time complexity because of massive redundant calculations. When calculating climbStairsRecursive(5), here's what happens:
climbStairsRecursive(5) calls climbStairsRecursive(4) and climbStairsRecursive(3)
climbStairsRecursive(4) calls climbStairsRecursive(3) and climbStairsRecursive(2)
Now climbStairsRecursive(3) is calculated twice
climbStairsRecursive(3) calls climbStairsRecursive(2) and climbStairsRecursive(1)
climbStairsRecursive(2) gets calculated 3 times total
For just n=5, we make 9 function calls when we only need 5 unique calculations. As n grows, this redundancy explodes exponentially - climbStairsRecursive(30) would require over a few million function calls! The time complexity becomes O(2^n), making it inefficient and impractical for larger values of n.
Dynamic programming eliminates this redundant computation through two main approaches:
Memoization stores the results of expensive function calls and returns the cached result when the same inputs occur again:
function climbStairsMemo(n, memo = {}) {
// If already calculated, return cached value
if (memo[n] !== undefined) {
return memo[n];
}
// Base cases: 1 way for 1 step, 2 ways for 2 steps
if (n <= 2) {
return n;
}
// Calculate once and store in memo for future use
memo[n] =
climbStairsMemo(n - 1, memo) +
climbStairsMemo(n - 2, memo);
return memo[n];
}
Memoization is so much more efficient because each unique value from 1 to n is calculated exactly once. When we need climbStairsMemo(3) again, instead of recalculating it (which would trigger more recursive calls), we simply look it up in our memo dictionary in O(1) time.
Let's trace through the execution of climbStairsMemo(5) with the top-down approach to see how memoization eliminates redundant work:
Call: climbStairsMemo(5)
memo = {} (empty)
Call: climbStairsMemo(4)
memo = {} (empty)
Call: climbStairsMemo(3)
memo = {} (empty)
Call: climbStairsMemo(2) → returns 2 (base case)
Call: climbStairsMemo(1) → returns 1 (base case)
Result: 2 + 1 = 3
memo = {3: 3} (stored!)
Call: climbStairsMemo(2) → returns 2 (base case)
Result: 3 + 2 = 5
memo = {3: 3, 4: 5} (stored!)
Call: climbStairsMemo(3) → returns 3 (FROM MEMO - no recursion!)
Result: 5 + 3 = 8
memo = {3: 3, 4: 5, 5: 8}
Efficiency comparison
Naive recursive: Makes 9 function calls with repeated calculations
Memoization: Makes only 5 unique calculations, then reuses stored results
Time complexity: Reduced from O(2^n) to O(n) since we make only n unique calculations
Space complexity: O(n) for the memo storage and call stack
Real impact: climbStairsMemo(30) drops from millions of function calls to about 30 unique calculations!
Tabulation builds the solution from the ground up, filling a table with solutions to subproblems:
function climbStairsTabulation(n) {
if (n <= 2) {
return n;
}
// Create an array to store solutions from 0 to n
const dp = new Array(n + 1).fill(0);
// Base cases
dp[1] = 1; // 1 way to reach step 1
dp[2] = 2; // 2 ways to reach step 2
// Build up the solution iteratively
for (let i = 3; i <= n; i++) {
// Ways to reach step i = ways to reach (i-1) + ways to reach (i-2)
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Tabulation eliminates recursion entirely by building the solution iteratively from the smallest subproblems up to the target.
Let's see the bottom-up approach in action to see how we build the solution systematically. Here's the iterative construction for climbStairsTabulation(5):
Initial state:
dp = [0, 1, 2, 0, 0, 0]
[0, 1, 2, 3, 4, 5] ← indices (step numbers)
Step by step construction:
i = 3:
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp = [0, 1, 2, 3, 0, 0]
i = 4:
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp = [0, 1, 2, 3, 5, 0]
i = 5:
dp[5] = dp[4] + dp[3] = 5 + 3 = 8
dp = [0, 1, 2, 3, 5, 8]
Final result: dp[5] = 8
Key advantages of tabulation
No recursion overhead: Unlike memoization, there's no recursive call stack.
Predictable execution: We calculate values in a predetermined order (1, 2, 3, 4, 5...).
Cache-friendly: Sequential array access optimizes memory usage.
Easy to optimize: Can reduce space complexity to O(1) since we only need the last two values.
function climbStairsOptimized(n) {
if (n <= 2) {
return n;
}
// Store only the last two results to save space
let prev2 = 1; // ways to reach step 1
let prev1 = 2; // ways to reach step 2
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
// Shift values forward
prev2 = prev1;
prev1 = current;
}
return prev1;
}
Efficiency comparison
Naive recursive: 9 function calls for n=5, exponential growth.
Tabulation: 3 simple additions for n=5, linear growth.
Time complexity: O(n) instead of O(2^n).
Space complexity: O(n) for the array, or O(1) with optimization.
Predictable performance: No risk of stack overflow for large inputs.
Both approaches reduce the time complexity from exponential O(2^n) to linear O(n), a dramatic improvement that makes the difference between solving the problem in milliseconds versus waiting years for larger inputs.
Dynamic programming has widespread applications in computer science and beyond:
Route Optimization: GPS systems use dynamic programming algorithms to find shortest paths between locations.
Text Processing: Spell checkers and autocomplete features often rely on dynamic programming to calculate edit distances between words.
Financial Modeling: Investment strategies and portfolio optimization frequently employ dynamic programming techniques.
Resource Allocation: The knapsack problem and its variants appear in scheduling, budgeting, and resource management.
The coin change problem is a classic coding challenge that, when solved using dynamic programming, demonstrates both of DP's key principles: optimal substructure and overlapping subproblems.
The coin change problem asks, "What's the minimum number of coins needed to make a target amount?"
Here's one solution using dynamic programming:
function minCoins(amount, coins) {
// Create dp array from 0 to amount, filled with Infinity
const dp = new Array(amount + 1).fill(Infinity);
// Base case: 0 coins needed to make amount 0
dp[0] = 0;
// Build up from 1 to target amount
for (let i = 1; i <= amount; i++) {
// Try each coin denomination
for (let coin of coins) {
// Only use coin if it is not larger than current amount
if (coin <= i) {
// Choose the minimum: current value OR solution for remaining amount + 1 coin
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// Return result if possible, -1 if impossible (infinity)
return dp[amount] === Infinity ? -1 : dp[amount];
}
/*
Example usage:
coins = [1, 3, 4], amount = 6
dp[0] = 0
dp[1] = dp[0] + 1 = 1
dp[2] = dp[1] + 1 = 2
dp[3] = min(dp[2]+1, dp[0]+1) = min(2+1, 0+1) = 1
dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = min(1+1, 1+1, 0+1) = 1
dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = min(1+1, 2+1, 1+1) = 2
dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(2+1, 1+1, 2+1) = 2
Result: 2 coins (3 + 3)
*/
And here's how the dynamic programming coin change algorithm works step by step for coins = [1, 3, 4], amount = 6:
Initial state:
dp = [0, ∞, ∞, ∞, ∞, ∞, ∞]
[0, 1, 2, 3, 4, 5, 6] ← amounts
Building up the solution:
For amount = 1:
Try coin 1: dp[1] = min(∞, dp[0] + 1) = min(∞, 0 + 1) = 1
dp = [0, 1, ∞, ∞, ∞, ∞, ∞]
For amount = 2:
Try coin 1: dp[2] = min(∞, dp[1] + 1) = min(∞, 1 + 1) = 2
dp = [0, 1, 2, ∞, ∞, ∞, ∞]
For amount = 3:
Try coin 1: dp[3] = min(∞, dp[2] + 1) = min(∞, 2 + 1) = 3
Try coin 3: dp[3] = min(3, dp[0] + 1) = min(3, 0 + 1) = 1
dp = [0, 1, 2, 1, ∞, ∞, ∞]
For amount = 4:
Try coin 1: dp[4] = min(∞, dp[3] + 1) = min(∞, 1 + 1) = 2
Try coin 3: dp[4] = min(2, dp[1] + 1) = min(2, 1 + 1) = 2
Try coin 4: dp[4] = min(2, dp[0] + 1) = min(2, 0 + 1) = 1
dp = [0, 1, 2, 1, 1, ∞, ∞]
For amount = 5:
Try coin 1: dp[5] = min(∞, dp[4] + 1) = min(∞, 1 + 1) = 2
Try coin 3: dp[5] = min(2, dp[2] + 1) = min(2, 2 + 1) = 2
Try coin 4: dp[5] = min(2, dp[1] + 1) = min(2, 1 + 1) = 2
dp = [0, 1, 2, 1, 1, 2, ∞]
For amount = 6:
Try coin 1: dp[6] = min(∞, dp[5] + 1) = min(∞, 2 + 1) = 3
Try coin 3: dp[6] = min(3, dp[3] + 1) = min(3, 1 + 1) = 2
Try coin 4: dp[6] = min(2, dp[2] + 1) = min(2, 2 + 1) = 2
dp = [0, 1, 2, 1, 1, 2, 2]
Final result: dp[6] = 2 (achieved with coins 3 + 3)
This solution demonstrates both key principles of dynamic programming. It has overlapping subproblems because finding the minimum coins for amount 6 requires knowing the solutions for amounts 5, 3, and 2. These same subproblems appear when calculating other amounts. It has optimal substructure because the optimal solution for any amount incorporates optimal solutions for smaller amounts. If we know the minimum coins for amount 3 is 1, then one way to make amount 6 is to use that solution plus one more coin of value 3.
Without DP, we'd need to try every possible combination of coins - an exponential number of possibilities. With DP, we build up the solution systematically:
Time complexity: O(amount × number of coins) instead of exponential.
Space complexity: O(amount) for the dp array.
No redundant work: Each subproblem (finding minimum coins for each amount) is solved exactly once.
Reusable results: Once we know the minimum coins for amount 3, we use this knowledge for all larger amounts that can benefit from it.
Dynamic programming is effective when:
The problem can be broken down into overlapping subproblems.
The problem exhibits optimal substructure.
A naive recursive solution would involve repeated calculations.
You need to optimize for time complexity at the cost of space complexity.
Common dynamic programming patterns include optimization problems (finding minimum/maximum values), counting problems (number of ways to achieve something), and decision problems that can be broken down into smaller decisions.
Dynamic programming transforms complex problems into manageable ones by systematically storing and reusing solutions to subproblems. Understanding this technique opens the door to solving a wide range of computational challenges efficiently.
What are the two key conditions that must be present for dynamic programming to be applicable?
Fast execution and low memory usage.
Think about what makes a problem suitable for dynamic programming optimization.
Overlapping subproblems and optimal substructure.
Recursive calls and iterative loops.
Think about what makes a problem suitable for dynamic programming optimization.
Memoization and tabulation.
Think about what makes a problem suitable for dynamic programming optimization.
2
What is the main difference between memoization and tabulation approaches in dynamic programming?
Memoization uses more memory than tabulation.
Consider the direction in which each approach builds the solution.
Tabulation is always faster than memoization.
Consider the direction in which each approach builds the solution.
Memoization is top-down while tabulation is bottom-up.
Memoization only works with recursive functions.
Consider the direction in which each approach builds the solution.
3
In the naive recursive climbing stairs implementation, what is the time complexity and why is it inefficient?
O(n) because it calculates each step once.
Think about how many times the same stair counts get calculated in the recursive tree.
O(n²) because it uses nested loops.
Think about how many times the same stair counts get calculated in the recursive tree.
O(2^n) because it recalculates the same subproblems multiple times.
O(log n) because it divides the problem in half.
Think about how many times the same stair counts get calculated in the recursive tree.
3