Dynamic Programming — Chapter Quiz · Data Structures & Algorithms

Question 1

1

Which two properties must a problem have for dynamic programming to apply?

AGreedy choice property and matroid structureBOverlapping subproblems and optimal substructureCSorted input and monotone predicateDA DAG representation and topological order

Overlapping subproblems means the same smaller instances are solved multiple times. Optimal substructure means an optimal solution to the whole can be built from optimal solutions to its parts. Both together enable DP.

Question 2

2

What is the key difference between top-down (memoization) and bottom-up (tabulation) DP?

ATop-down is always faster because it skips unreachable statesBTop-down uses recursion with a memo cache (only computes needed states); bottom-up iteratively fills a table from smaller to larger subproblemsCBottom-up always uses more memory than top-downDThey solve different types of problems

Memoization is lazy — it only computes a subproblem when first needed and caches the result. Tabulation is eager — it fills every cell in dependency order. Top-down can be faster when many states are unreachable; bottom-up avoids recursion overhead.

Question 3

3

In the 0/1 knapsack problem with n items and capacity W, the DP table has dimensions:

An × nBW × WC(n+1) × (W+1)Dn × log W

dp[i][w] represents the best value using the first i items with capacity w. Including the base cases (0 items or 0 capacity), the table is (n+1) × (W+1). Time and space are both O(n·W).

Question 4

4

The LCS (Longest Common Subsequence) recurrence for strings X and Y at position (i, j) is:

Adp[i][j] = dp[i-1][j-1] + 1 if X[i] === Y[j], else 0Bdp[i][j] = dp[i-1][j-1] + 1 if X[i] === Y[j], else Math.max(dp[i-1][j], dp[i][j-1])Cdp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1Ddp[i][j] = dp[i-1][j] + dp[i][j-1]

When characters match, extend the LCS from the diagonal. When they don't match, take the best of skipping one character from either string. This gives the O(m·n) classic DP.

Question 5

5

The naive O(n²) LIS (Longest Increasing Subsequence) algorithm can be improved to O(n log n) by:

ASorting the array first and running LCS against the sorted versionBMaintaining a patience-sorting "pile" array and binary searching for the correct position of each elementCUsing a monotonic stack to track decreasing elementsDRunning BFS on the DAG of valid transitions

The patience sorting insight: maintain a tails array where tails[i] is the smallest tail of all increasing subsequences of length i+1. For each element, binary search tails to find where to place it. The length of tails is the LIS length.

Question 6

6

Edit distance (Levenshtein distance) can be computed in O(m·n) time and O(min(m,n)) space.

TTrueFFalse

The standard 2-row (or 1-row with careful updates) optimisation reduces space from O(m·n) to O(min(m,n)) because each row only depends on the previous row.

Question 7

7

In a Fibonacci DP solution, bottom-up tabulation can be further optimised to use only O(___) space by keeping just the last two values.

Each Fibonacci number depends only on the previous two. Instead of a full array, two variables (prev and curr) suffice, reducing space from O(n) to O(1).

Question 8

8

Which of the following problems are correctly solved by dynamic programming? (Select all that apply)

Select all that apply.

ACoin change (minimum coins to make amount W)BMatrix chain multiplication (minimum parenthesisation cost)CFinding a cycle in a directed graphDComputing the number of unique paths in a grid from top-left to bottom-right

Coin change, matrix chain, and grid paths all exhibit overlapping subproblems and optimal substructure. Cycle detection (DFS with colouring) is a graph algorithm, not a DP problem.

Test what you learned.