2D Dynamic Programming: LCS & Knapsack

Every 1D DP problem so far tracked progress with a single number, how many steps climbed, how much of the target amount reached. Some problems need to track two independent kinds of progress at once, and for those, a single dp array is not enough. The state needs a grid, with one dimension for each kind of progress. Two of the most common examples are comparing two sequences, and choosing among items under a shared budget.

The longest common subsequence (LCS) of two strings a and b is the longest sequence of characters that appears in both, in the same relative order, but not necessarily contiguously. Progress here has two independent axes, how far into a you have compared, and how far into b, so the state is naturally dp[i][j]: the length of the LCS of the first i characters of a and the first j characters of b. If the current characters match, they extend the best subsequence found one step back on both axes. If they do not match, the best answer just carries forward whichever of "drop this character of a" or "drop this character of b" was already better.

0/1 knapsack asks: given items with weights and values, and a capacity limit, what is the maximum total value achievable without exceeding the capacity, using each item at most once? Progress here also has two axes, how many items have been considered so far, and how much capacity remains, so dp[i][cap] holds the best achievable value using only the first i items with capacity cap available. For each item, the choice is binary: leave it out entirely (carry forward dp[i-1][cap] unchanged), or include it if it fits (add its value to whatever was achievable with the remaining capacity before considering it, dp[i-1][cap - weight] + value), and take whichever of those two is larger.

• -Whenever a problem's "progress" naturally has two independent measurements (two string positions, or items-considered vs. capacity-used), the dp state is a 2D grid, not a 1D array.
• -LCS's recurrence looks one step diagonally back (both indices decrease) on a match, and one step back on either axis (whichever is better) on a mismatch.
• -Knapsack's recurrence always compares "skip this item" against "take this item," never both at once. That binary choice is exactly what "0/1" refers to in the name.
• -Both tables are filled row by row (or item by item), left to right, since each cell only depends on cells already computed above or to the left.