CS: Dynamic Programming: Memoization and Tabulation
Solving overlapping subproblems with saved results
CS: Dynamic Programming: Memoization and Tabulation
Solving overlapping subproblems with saved results
CS - Grade 9-12
- 1
In your own words, explain what dynamic programming is and name the two main properties a problem usually needs in order for dynamic programming to be useful.
Think about avoiding repeated work and building a large answer from smaller answers.
Dynamic programming is a technique for solving a problem by breaking it into smaller subproblems, solving each subproblem once, and saving the results for reuse. It is useful when a problem has overlapping subproblems and optimal substructure. - 2
A recursive Fibonacci function calls fib(n - 1) and fib(n - 2) until it reaches fib(0) or fib(1). Explain why this plain recursive version does repeated work.
The plain recursive Fibonacci function does repeated work because the same smaller values are computed many times. For example, fib(5) needs fib(4) and fib(3), and fib(4) also needs fib(3), so fib(3) is recomputed. - 3
For the Fibonacci sequence where fib(0) = 0 and fib(1) = 1, fill in the tabulation values from fib(0) through fib(7).
Each value after the first two is the sum of the two values before it.
The table values are fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, fib(5) = 5, fib(6) = 8, and fib(7) = 13. - 4
Compare memoization and tabulation. State one similarity and one difference between the two approaches.
Memoization and tabulation both save subproblem results so they do not have to be recomputed. A difference is that memoization is usually top-down with recursion, while tabulation is usually bottom-up with loops. - 5
The following pseudocode uses memoization: function fib(n): if n is in memo: return memo[n] if n <= 1: return n memo[n] = fib(n - 1) + fib(n - 2) return memo[n] If fib(6) is called with an empty memo, what final key-value pairs should be stored in memo for n from 2 through 6?
Work upward from the base cases even though the code is recursive.
The memo should store 2: 1, 3: 2, 4: 3, 5: 5, and 6: 8. The base cases fib(0) and fib(1) may not be stored because the pseudocode returns them directly before saving them. - 6
A student says, "Memoization always uses less memory than tabulation because it only computes what it needs." Explain why this statement is not always true.
The statement is not always true because memoization can still end up storing many or all subproblems. It also uses the recursion call stack, while tabulation can sometimes be optimized to store only a few recent values. - 7
You can climb a staircase by taking either 1 step or 2 steps at a time. Let ways(n) be the number of ways to climb n steps. Write the recurrence relation and base cases for this problem.
Focus on the last move used to reach the top.
The recurrence is ways(n) = ways(n - 1) + ways(n - 2), because the last move is either a 1-step move from step n - 1 or a 2-step move from step n - 2. Useful base cases are ways(0) = 1 and ways(1) = 1. - 8
Using the staircase recurrence ways(n) = ways(n - 1) + ways(n - 2), ways(0) = 1, and ways(1) = 1, compute ways(2) through ways(5) using tabulation.
The tabulation gives ways(2) = 2, ways(3) = 3, ways(4) = 5, and ways(5) = 8. Each value is found by adding the two previous values. - 9
A coin change problem asks for the minimum number of coins needed to make a target amount using coin values 1, 3, and 4. Let dp[x] be the minimum number of coins needed for amount x. Write a recurrence for dp[x].
Think about choosing the last coin added to the solution.
A correct recurrence is dp[x] = 1 + min(dp[x - 1], dp[x - 3], dp[x - 4]) for the terms where the amount is not negative. The base case is dp[0] = 0 because zero coins are needed to make amount 0. - 10
Using coins 1, 3, and 4 with dp[0] = 0, find the minimum number of coins needed to make amount 6. Show the best combination.
The minimum number of coins needed to make 6 is 2. The best combination is 3 + 3, which uses two coins. - 11
A longest common subsequence problem compares strings A = "ABC" and B = "AC". What is the length of the longest common subsequence, and what is one such subsequence?
A subsequence keeps the original order but does not have to use adjacent characters.
The longest common subsequence has length 2. One such subsequence is "AC" because A and C appear in order in both strings. - 12
For Fibonacci, explain how a tabulation solution can be changed from using an array of size n + 1 to using only constant extra space.
The recurrence only looks back two positions.
A tabulation solution can use constant extra space by keeping only the two most recent Fibonacci values instead of the whole array. At each step, the next value is the sum of the previous two, then the stored values are shifted forward.