2-D DP

Reach for it when

• Compare two sequences (LCS, edit distance)
• Paths in a grid
• Knapsack: items and a budget

Core idea

dp[i][j] answers the subproblem for prefixes s[:i] and t[:j] (or cell (i, j)). Each cell depends on its neighbors up, left, and up-left, so fill row by row. Rolling arrays reduce space to one or two rows.

Template · O(m * n) time, O(n) with a rolling row

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[-1][-1]

int lcs(const string& a, const string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1
                                            : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

Common pitfalls

• Off-by-one between dp indices and string indices
• 0/1 knapsack in 1-D must iterate capacity downward
• [[0] * n] * m aliases rows in Python

Practice · 0 / 12 done

• Best Time to Buy And Sell Stock With CooldownMedium
• Coin Change IIMedium
• Edit DistanceMedium
• Interleaving StringMedium
• Longest Common SubsequenceMedium
• Predict the WinnerMedium
• Target SumMedium
• Unique PathsMedium
• Burst BalloonsHard
• Distinct SubsequencesHard
• Longest Increasing Path In a MatrixHard
• Regular Expression MatchingHard