Dynamic
Programming

Naive recursion — O(2ⁿ)

The recursion tree explodes exponentially. fib(40) makes over one billion calls.

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

Call tree for fib(5)

DP approach — O(n)

Space-optimised solution

def fib(n):
    if n <= 1: return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

Example: Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways to reach step n?

# State: dp[i] = ways to reach step i
# Recurrence: dp[i] = dp[i-1] + dp[i-2]
# Base: dp[0] = 1, dp[1] = 1
# Order: left to right
# Answer: dp[n]

def climb_stairs(n):
    if n <= 1: return 1
    prev2, prev1 = 1, 1
    for i in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

Given coins of denominations coins[] and a target amount, find the minimum number of coins needed.

Recurrence

dp[0] = 0  # base case
dp[amount] = min(dp[amount - coin] + 1)
             for coin in coins
             if amount - coin >= 0

Full solution

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Trace: coins = [1, 3, 4], amount = 6

Given an array nums[], find the length of the longest strictly increasing subsequence (LIS).

O(n²) DP approach

# State: dp[i] = length of LIS ending at index i
# Recurrence: dp[i] = max(dp[j] + 1)
#             for all j < i where nums[j] < nums[i]
# Base: dp[i] = 1 for all i

def lis(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

O(n log n) with patience sorting

import bisect

def lis_fast(nums):
    tails = []  # tails[i] = smallest tail of
                # all increasing subseqs of length i+1
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

Trace: [10, 9, 2, 5, 3, 7, 101, 18]

Minimum insertions, deletions, and substitutions to transform string a into string b.

Recurrence

# State: dp[i][j] = edit distance between
#        a[0..i-1] and b[0..j-1]

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

Full solution

def edit_distance(a, b):
    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]

DP table: "kitten" → "sitting"

Find the length of the longest subsequence common to two strings a and b. Characters need not be contiguous but must preserve order.

Recurrence

# State: dp[i][j] = LCS length of a[0..i-1], b[0..j-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])

Solution

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    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] + 1
            else:
                dp[i][j] = max(dp[i-1][j],
                               dp[i][j-1])
    return dp[m][n]

Recovering the LCS string

def recover_lcs(a, b, dp):
    i, j = len(a), len(b)
    result = []
    while i > 0 and j > 0:
        if a[i-1] == b[j-1]:
            result.append(a[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))

Example

Given matrices A1...An with dimensions p[0]×p[1], p[1]×p[2], ..., p[n-1]×p[n], find the parenthesisation that minimises total scalar multiplications.

Recurrence

# State: dp[i][j] = min cost to multiply A_i..A_j
# Recurrence:
dp[i][j] = min over k in [i, j):
    dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]

# Base: dp[i][i] = 0 (single matrix, no cost)

Solution

def matrix_chain(p):
    n = len(p) - 1
    dp = [[0]*n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = (dp[i][k] + dp[k+1][j]
                        + p[i]*p[k+1]*p[j+1])
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

Example: p = [10, 30, 5, 60]

Matrices: A₁(10×30), A₂(30×5), A₃(5×60)

Longest Palindromic Subsequence

# dp[i][j] = LPS length of s[i..j]
if s[i] == s[j]:
    dp[i][j] = dp[i+1][j-1] + 2
else:
    dp[i][j] = max(dp[i+1][j], dp[i][j-1])

# Iterate by increasing length
# Time: O(n^2), Space: O(n^2) → O(n)

Palindrome Partitioning

# dp[i] = min cuts for s[0..i] to be
#         all palindromes
dp[i] = min(dp[j-1] + 1)
        for j in [0..i] where s[j..i]
        is a palindrome

# Pre-compute is_pal[i][j] with DP
# Time: O(n^2), Space: O(n^2)

Distinct Subsequences

Count the number of distinct subsequences of s that equal t.

# dp[i][j] = ways to form t[0..j-1]
#            from s[0..i-1]
if s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
else:
    dp[i][j] = dp[i-1][j]

# Time: O(mn), Space: O(mn) → O(n)

Regular Expression Matching

# dp[i][j] = does s[0..i-1] match p[0..j-1]?
# Handle '.', '*' with careful transitions
# Time: O(mn), Space: O(mn)

Tree DP computes values at each node based on its children, via post-order DFS. The state is typically dp[node] or dp[node][choice].

Maximum Independent Set

Select nodes with maximum total weight such that no two adjacent nodes are selected.

# dp[v][0] = max if v is NOT selected
# dp[v][1] = max if v IS selected

dp[v][0] = sum(max(dp[c][0], dp[c][1])
               for c in children(v))

dp[v][1] = weight[v] +
           sum(dp[c][0]
               for c in children(v))

# Answer: max(dp[root][0], dp[root][1])

Tree Diameter

# dp[v] = longest path starting at v
#         going downward
dp[v] = max(dp[c] + 1 for c in children(v))

# At each node, diameter candidate =
# sum of two longest downward paths
diameter = max(top1 + top2)
           across all nodes

Rerooting Technique

When the state involves a subset of n elements (n ≤ 20–25), represent the subset as a bitmask integer. State: dp[mask] or dp[mask][i].

Travelling Salesman Problem (TSP)

# dp[mask][i] = min cost to visit cities in
# 'mask' ending at city i

# Base: dp[1 << start][start] = 0

for mask in range(1, 1 << n):
    for i in range(n):
        if not (mask & (1 << i)): continue
        for j in range(n):
            if mask & (1 << j): continue
            new_mask = mask | (1 << j)
            dp[new_mask][j] = min(
                dp[new_mask][j],
                dp[mask][i] + dist[i][j]
            )

# Answer: min(dp[(1<