Dynamic programming: 2D

The idea

When solving problems like Edit Distance or Longest Common Subsequence, our state depends on two variables (an index in string A, and an index in string B). This means our DP cache is a 2D grid.

Edit Distance: Minimum operations (insert, delete, replace) to turn word1 into word2. For any cell dp[i][j], if the characters match, the cost is dp[i-1][j-1]. If they don't, we take 1 + min(insert, delete, replace) by looking at our left, top, and top-left neighbours.

How it works (Edit Distance)

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
        
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],    # Delete
                                   dp[i][j - 1],    # Insert
                                   dp[i - 1][j - 1])# Replace
    return dp[m][n]