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.