Work through five foundational dynamic programming problems — Fibonacci, coin change, 0-1 knapsack, LCS, and LIS.

Classic DP Problems

These five problems are the foundation of dynamic programming. Master these and you can recognize the patterns in hundreds of variations.

Classic DP Problems

dp table

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

fibonacci.py

dp = [0]*(n+1); dp[1] = 1

# base cases: dp[0]=0, dp[1]=1

dp[i] = dp[i-1] + dp[i-2]

return dp[n]

Fibonacci — fill dp[0..9]

step 0/18

1. Fibonacci sequence

The simplest DP problem — each number is the sum of the two before it.

State:  dp[i] = i-th Fibonacci number
Base:   dp[0] = 0, dp[1] = 1
Recur:  dp[i] = dp[i-1] + dp[i-2]

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

2. Coin change — minimum coins

Given coin denominations and a target, find the minimum coins needed.

State:  dp[i] = min coins to make amount i
Base:   dp[0] = 0
Recur:  dp[i] = min(dp[i - coin] + 1) for each coin ≤ 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 and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

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


print(coin_change([1, 5, 10, 25], 36))   # 3 → 25+10+1
print(coin_change([1, 3, 4], 6))         # 2 → 3+3

3. 0/1 Knapsack

Given items with weights and values and a weight capacity, maximize the total value.

State:  dp[i][w] = max value using first i items with capacity w
Base:   dp[0][w] = 0, dp[i][0] = 0
Recur:  dp[i][w] = max(dp[i-1][w],           # skip item i
                        dp[i-1][w - weight[i]] + value[i])  # take item 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):
            # skip item i
            dp[i][w] = dp[i-1][w]

            # take item i — if it fits
            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 = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack(weights, values, 8))   # 10 → items 0 and 2 (weights 2+4, values 3+5... wait 4+6=10) → items 1,3

The "0/1" in 0/1 Knapsack means each item can be taken at most once — either you take it (1) or you leave it (0). The unbounded knapsack variant allows taking items multiple times — the recurrence changes slightly: dp[w] = max(dp[w], dp[w - weight] + value) in a single 1D array.

4. Longest Common Subsequence (LCS)

Find the longest sequence of characters present in both strings, not necessarily contiguous.

State:  dp[i][j] = LCS length of s1[:i] and s2[:j]
Base:   dp[0][j] = 0, dp[i][0] = 0
Recur:  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])

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", "BDCABA"))   # 4
print(lcs("intention", "execution"))   # 5

5. Longest Increasing Subsequence (LIS)

Find the length of the longest subsequence where each element is strictly greater than the previous.

Input:  [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4  →  [2, 3, 7, 101]

State:  dp[i] = length of LIS ending at index i
Base:   dp[i] = 1 for all i (each element alone is a subsequence of length 1)
Recur:  dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]

def lis(arr):
    n = len(arr)
    dp = [1] * n   # every element alone is a subsequence of length 1

    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)


arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis(arr))   # 4 → [2, 3, 7, 101] or [2, 5, 7, 101]

The O(n²) solution above is clear and sufficient for most interviews. There is also an O(n log n) solution using binary search — it maintains a "patience sorting" array where each element is placed in the right position using binary search. The length of this array at the end equals the LIS length.

Patterns summary

Problem	State dimensions	Key decision
Fibonacci	1D (n)	Sum of two previous
Coin change	1D (amount)	Which coin to use last
0/1 Knapsack	2D (items, capacity)	Take or skip each item
LCS	2D (i, j)	Match or skip each character
LIS	1D (ending index)	Extend which previous subsequence

Complexity

Problem	Time	Space	Space (optimized)
Fibonacci	O(n)	O(n)	O(1)
Coin change	O(n × coins)	O(n)	O(n)
0/1 Knapsack	O(n × W)	O(n × W)	O(W)
LCS	O(m × n)	O(m × n)	O(min(m,n))
LIS (basic)	O(n²)	O(n)	O(n)
LIS (optimized)	O(n log n)	O(n)	O(n)

Classic DP Problems

On this page