Dynamic Programming — Concepts, Algorithms & Examples

You're standing at the bottom of a staircase. You can take 1 or 2 steps at a time. How many ways can you reach the top? If you try to brute-force this, you end up computing the same sub-problems hundreds of times. Dynamic Programming says: solve each sub-problem once, remember the answer, and reuse it. That single idea is worth a thousand interviews.

What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique for solving problems by breaking them into overlapping sub-problems, solving each sub-problem only once, and storing the result so it can be reused. It is most applicable when a problem has two properties:

• Optimal Substructure: The optimal solution of the problem can be built from optimal solutions of its sub-problems.
• Overlapping Sub-problems: The same sub-problems are solved multiple times during a naive recursive approach.

Two Ways to Implement DP

Both approaches give the same answer. Choose memoization when the recursion is natural and not all sub-problems are needed. Choose tabulation when you want a clean iterative solution with O(1) space optimization potential.

Warm-Up: Fibonacci Numbers

The classic entry point into DP. The naive recursion is O(2ⁿ). DP drops it to O(n).

Naive Recursion — O(2ⁿ)

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

# fib(6) recomputes fib(2) five times, fib(3) three times…
# For n = 40: ~2 billion calls!

Top-Down DP (Memoization) — O(n) time, O(n) space

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# Each value computed exactly once, stored in cache.
# fib_memo(40) → instant.

Bottom-Up DP (Tabulation) — O(n) time, O(n) space

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

# dp table for n = 6:
# Index: 0  1  2  3  4  5  6
# Value: 0  1  1  2  3  5  8

Space-Optimised — O(n) time, O(1) space

def fib_opt(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Only two variables needed — no full table required.

Problem 1: Climbing Stairs

You can climb 1 or 2 steps at a time. Given n stairs, how many distinct ways can you reach the top?

Recurrence: ways(n) = ways(n-1) + ways(n-2) — identical structure to Fibonacci.

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

# climb_stairs(5) → 8

Problem 2: Coin Change (Minimum Coins)

Given coin denominations and a target amount, find the minimum number of coins needed to make that amount. If it's impossible, return -1.

Example: coins = [1, 3, 4], amount = 6 → answer is 2 (3 + 3).

Recurrence: dp[i] = min(dp[i - c] + 1) for each coin c where c ≤ i.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 3, 4], 6))    # → 2  (3+3)
print(coin_change([2], 3))           # → -1 (impossible)
print(coin_change([1, 5, 6, 9], 11)) # → 2  (5+6)

Problem 3: 0/1 Knapsack

Given n items, each with a weight and value, and a bag with capacity W — find the maximum value you can carry. Each item can be taken at most once.

Recurrence:

• If item weight > remaining capacity: dp[i][w] = dp[i-1][w]
• Else: dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i]] + val[i])

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if weights[i - 1] <= w:
                take = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], take)

    return dp[n][capacity]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity))  # → 9

Problem 4: Longest Common Subsequence (LCS)

Given two strings, find the length of their longest common subsequence — characters that appear in the same relative order in both strings (not necessarily contiguous).

Example: s1 = "ABCBDAB", s2 = "BDCAB" → LCS = "BCAB" (length 4).

Recurrence:

• If s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1] + 1
• Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[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]

print(lcs("ABCBDAB", "BDCAB"))   # → 4
print(lcs("AGGTAB", "GXTXAYB"))  # → 4
print(lcs("abcde", "ace"))        # → 3

Problem 5: Longest Increasing Subsequence (LIS)

Find the length of the longest subsequence of an array such that all elements are in strictly increasing order.

Example: [10, 9, 2, 5, 3, 7, 101, 18] → LIS = [2, 3, 7, 18] → length 4.

def lis(arr):
    n = len(arr)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # → 4
print(lis([0, 1, 0, 3, 2, 3]))             # → 4
print(lis([7, 7, 7, 7]))                   # → 1

Problem 6: Matrix Chain Multiplication

Given a chain of matrices, find the most efficient order of multiplication to minimise the total number of scalar multiplications.

Recurrence: dp[i][j] = min over all k of (dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])

def matrix_chain(p):
    n = len(p) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            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-1] * p[k] * p[j]
                dp[i][j] = min(dp[i][j], cost)

    return dp[1][n]

p = [40, 20, 30, 10, 30]
print(matrix_chain(p))  # → 26000

How to Approach Any DP Problem

Common DP Patterns to Recognise

Complexity Summary

Dynamic Programming is one of those topics that clicks suddenly — and once it does, you start seeing DP everywhere. Start with Fibonacci, then Climbing Stairs, then Coin Change. Work through Knapsack and LCS with pen and paper, filling the table manually. That muscle memory of "define state → write recurrence → fill table" is all you need to crack any DP problem, in any interview, at any company.