Comprehensive Tutorial on Dynamic Programming

What Is Dynamic Programming?

Dynamic Programming (DP) breaks complex problems into smaller overlapping sub-problems, solving each only once and storing its result — via memoisation (top-down) or tabulation (bottom-up).

Top-Down vs Bottom-Up

Example 1 — Fibonacci Numbers

The Fibonacci sequence is the traditional first DP problem. Its naive recursive implementation is O(2ⁿ) — fixing it with DP gives O(n).

Approach A — Top-Down (Memoisation)

import sys
sys.setrecursionlimit(10000)
# memo dictionary stores already-computed results
memo = {}
def fib_memo(n):
    if n <= 1: return n
    if n in memo: return memo[n]   # cache hit
    memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]
print([fib_memo(i) for i in range(10)])

Approach B — Bottom-Up (Tabulation)

def fib_dp(n):
    if n <= 1: return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]  # recurrence
    return dp[n]

Example 2 — 0/1 Knapsack Problem

The 2-D table captures all possibilities. Row i asks: "What if I could only use items 1…i?" Column w asks: "What if my capacity were exactly w kg?" For each cell (i, w) we face a binary choice — take item i or skip it — and record the better option. Because row i only depends on row i−1, the table can be space-optimised to a single 1-D array filled in reverse.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(W+1):
            skip = dp[i-1][w]
            take = 0
            if weights[i-1] <= w:
                take = dp[i-1][w-weights[i-1]] + values[i-1]
            dp[i][w] = max(skip, take)
    return dp[n][W]

Example 3 — Longest Common Subsequence (LCS)

LCS is solved with a 2-D DP table. dp[i][j] stores the length of the longest common subsequence of the first i characters of X and the first j characters of Y. The table is filled row by row; each cell depends on at most three neighbours (diagonal, above, left), so the fill order is straightforward.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[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]

X,Y = "ABCB", "BDCB"  # LCS = "BCB", length 3

Example 4 — Coin Change (Minimum Coins)

The key insight: to make amount a using coin c, we need to already know how to make amount a−c optimally. By iterating a from 1 to amount (smallest to largest), every dp[a−c] we reference is already filled. We try every coin for every amount, keeping the minimum. This is an unbounded knapsack variant — coins can be reused any number of times.

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

Example 5 — Longest Increasing Subsequence (LIS)

Find the longest subsequence where each element is strictly greater than the previous. Elements need not be contiguous.

def lis_dp(arr):
    n = len(arr)
    dp   = [1] * n
    prev = [-1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j]+1 > dp[i]:
                dp[i] = dp[j]+1; prev[i]=j
    return max(dp)

Example 6 — Matrix Chain Multiplication

This is interval DP: the state spans a contiguous sub-range [i,j]. We try every possible split point k — meaning every possible place to put the last parenthesis — and take the minimum cost. The key is to fill by increasing chain length: a chain of length l depends only on sub-chains of length < l, which are already computed.

def matrix_chain(dims):
    n = len(dims)-1
    dp = [[0]*n for _ in range(n)]
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i+l-1; dp[i][j] = float('inf')
            for k in range(i,j):
                cost = dp[i][k]+dp[k+1][j]+dims[i]*dims[k+1]*dims[j+1]
                if cost<dp[i][j]: dp[i][j]=cost
    return dp[0][n-1]

Time & Space Complexity Reference

Every DP problem has two costs: time (how many states × how much work per state) and space (how big the table is). The table below shows both for each example in this tutorial, plus whether the space can be reduced. The “optimised space” column assumes you only need the final value, not the full traceback.

The 5-Step Framework

Every DP problem, regardless of domain, can be solved by following these five steps in order. Skipping steps — especially step 1 — is the leading cause of bugs in DP code. Work through a small example (3–4 elements) on paper before writing a single line of code.

DP Pattern Taxonomy

Recognising the pattern a problem belongs to is the fastest route to a solution. Most DP problems are disguised instances of one of six canonical patterns. Once you identify the pattern, the state definition, recurrence, and fill order follow almost mechanically.

Common Mistakes & How to Avoid Them

Most DP bugs fall into a small number of repeating categories. The table below shows the five most common mistakes, what symptom they produce, and the concrete fix. Recognising these patterns in your own code is worth more than memorising a hundred DP solutions.

Golden Rules of Dynamic Programming

These six rules distil hundreds of solved DP problems into actionable habits. They are not tips to memorise — they are habits to build through deliberate practice. Apply them on every new problem until they become automatic.