2D tables: grids, strings & knapsack

When a subproblem needs two indices: unique paths, edit distance, LCS, and 0/1 knapsack. · 12 min read

When you need two dimensions

Some subproblems are indexed by two things — a position in two strings, a cell in a grid, or (item, capacity). Then dp is a 2D table and each cell depends on a few neighbours.

Unique paths

How many ways to walk from the top-left of an R×C grid to the bottom-right, moving only right or down? Each cell is the sum of the cell above and the cell to its left: dp[i][j] = dp[i-1][j] + dp[i][j-1].

Interactive visualization: Unique paths — each cell adds up + left — step through it frame by frame on this page.

Edit distance

The minimum insert/delete/replace edits to turn a into b. If the current characters match, copy the diagonal; otherwise it's 1 + min(replace, delete, insert):

if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]
else:                dp[i][j] = 1 + min(dp[i-1][j-1],  # replace
                                          dp[i-1][j],    # delete
                                          dp[i][j-1])    # insert

Interactive visualization: Edit distance — the 3-way minimum — step through it frame by frame on this page.

Longest common subsequence

dp[i][j] = LCS length of the first i chars of a and first j of b. On a match, extend the diagonal by 1; otherwise take the best of dropping one character from either string.

0/1 knapsack

With items of weight/value and a capacity W, dp[i][w] = best value using the first i items within weight w. Either skip item i (dp[i-1][w]) or take it if it fits (dp[i-1][w - wt[i]] + val[i]).

for (int i = 1; i <= n; i++)
    for (int w = 0; w <= W; w++) {
        dp[i][w] = dp[i-1][w];                       // skip
        if (wt[i-1] <= w)
            dp[i][w] = max(dp[i][w], dp[i-1][w-wt[i-1]] + val[i-1]); // take
    }

Practice: Longest Common Subsequence (Hard) — Length of the longest subsequence shared by two strings (2D DP).

A curated path for dynamic programming

DP is the topic most people drill with a dedicated set. These two are the classic starting points:

• AtCoder Educational DP Contest (EDPC): 26 problems labelled A–Z that walk through the standard DP patterns — knapsack, LIS/LCS, interval DP, tree DP, and bitmask DP. The canonical DP practice set; pair it with this chapter.
• Codeforces blog #122422: a community-curated DP problem/learning list to keep practising after EDPC.
• More judges and general resources are in the CP intro.