CS: Dynamic Programming: Memoization and Tabulation Worksheet

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 3

For the Fibonacci sequence where fib(0) = 0 and fib(1) = 1, fill in the tabulation values from fib(0) through fib(7).

Accepted Answer

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.

Question 4

Compare memoization and tabulation. State one similarity and one difference between the two approaches.

Accepted Answer

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.

Question 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?

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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].

Accepted Answer

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.

Question 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.

Accepted Answer

The minimum number of coins needed to make 6 is 2. The best combination is 3 + 3, which uses two coins.

Question 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?

Accepted Answer

The longest common subsequence has length 2. One such subsequence is "AC" because A and C appear in order in both strings.

Question 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.

Accepted Answer

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.

CS: Dynamic Programming: Memoization and Tabulation

More CS Worksheets

More Grade 9-12 Worksheets