2-D Dynamic Programming
DP where the subproblem needs two indices — grid paths, two-string comparisons, and knapsack-style capacity constraints.
Try answering in your head first, then click a question to check the model answer.
Q1.Explain the recurrence relation for the longest common subsequence (LCS) DP solution.(show answer)
Define dp[i][j] as the LCS length of the first i characters of string A and first j characters of string B. If A[i-1] == B[j-1], the characters match, so dp[i][j] = dp[i-1][j-1] + 1. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — the best LCS ignoring either the current character of A or of B. Base case: dp[0][j] = dp[i][0] = 0 (an empty string has LCS length 0 with anything).
Q2.Walk through the 0/1 knapsack DP recurrence and explain the "0/1" part of the name.(show answer)
dp[i][w] = max value achievable using the first i items with capacity w. For item i (weight wt, value val): if wt > w, you can't include it, so dp[i][w] = dp[i-1][w]. Otherwise, take the better of excluding it (dp[i-1][w]) or including it (val + dp[i-1][w - wt]). "0/1" refers to each item being either fully included (1) or fully excluded (0) — unlike the fractional knapsack variant, which allows taking a partial amount of an item and is solvable greedily instead.
Q3.Why does a 2D grid "unique paths" DP problem (counting paths from top-left to bottom-right, moving only right or down) have the recurrence `dp[i][j] = dp[i-1][j] + dp[i][j-1]`?(show answer)
Since you can only move right or down, the only two ways to arrive at cell (i, j) are from directly above (i-1, j) or directly to the left (i, j-1) — so the number of distinct paths to (i, j) is the sum of the paths to those two predecessor cells. Base case: the first row and first column each have exactly 1 path (moving only right, or only down, respectively), since there's no alternative predecessor to sum from.
Q4.How would you reduce the space complexity of the unique-paths DP from O(m*n) to O(n)?(show answer)
Since dp[i][j] only depends on the row directly above it (dp[i-1][j]) and the current row so far (dp[i][j-1]), you don't need to keep every previous row — only the row currently being computed, updated left to right in place (reading the not-yet-overwritten value at position j as the "row above" value before overwriting it). This reduces memory from a full 2D table to a single 1D array of length n, without changing the O(m*n) time complexity.