Dynamic Programming — the shape behind dozens of interview problems.

Dynamic Programming in Python

def edit_distance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    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 a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

See language-specific tabs at /languages/python/patterns and the SQL variant at /languages/sql/patterns.

Related patterns

Frequently asked questions

What is the dynamic programming pattern?

Dynamic Programming is break an overlapping-subproblem problem into a recurrence and cache results. State × transition cost; typical O(n), O(n²), or O(n·m).

When should I use dynamic programming?

Use it when: The optimal substructure holds. Subproblems repeat (naive recursion is exponential). The answer can be phrased as min / max / count over a recurrence.

What are the most common dynamic programming bugs?

Confusing 0-indexed arrays with 1-indexed DP tables. Missing base cases on the first row/column. Computing transitions in the wrong order (depending on cells not yet filled).

What problems use the dynamic programming pattern?

Representative scenarios: Ski Lift Tolls — minimum-cost path on a grid. DNA Commonality — longest common subsequence. Typo Repair Cost — edit distance between strings.

Is dynamic programming on the Blind 75?

Yes — Dynamic Programming is one of the core patterns behind the Blind 75 list. See /blind-75 for the complete mapping.