Dynamic Programming

You might have heard that dynamic programming (DP) is one of the hardest topics in programming. Honestly? It gets a bad reputation. Once you understand the core idea, it becomes one of the most satisfying techniques to use. This guide will make it click - step by step, no scary math.

What is Dynamic Programming?

Dynamic programming is a technique for solving problems by breaking them into smaller subproblems - and crucially, saving the answers to those subproblems so you never solve the same one twice.

That last part is the key. The “dynamic” in DP doesn’t mean fancy or complex - it just means we’re building up answers from smaller pieces and storing them along the way.

Here’s a simple analogy: imagine you’re asked what 7 + 8 is. You think “15”. Now someone asks you 7 + 8 again five seconds later. You don’t re-add the numbers - you just remember the answer. That’s dynamic programming. Compute once, reuse forever.

DP works when a problem has two properties:

• Overlapping subproblems - the same smaller problem comes up again and again
• Optimal substructure - the best answer to the full problem can be built from the best answers to smaller pieces

Tip

If you’ve seen recursion, DP is basically “smarter recursion” - it remembers past results instead of recomputing them over and over.

Two Ways to Do DP

There are two main styles of writing DP solutions. Both work - they’re just different ways of thinking about the same idea.

Top-Down (Memoization)

Start from the big problem, break it into smaller pieces recursively, but cache (store) each answer the first time you compute it. If you see the same subproblem again, just return the cached answer.

This is the most natural style if you already know how to write recursive solutions. You literally take your recursive solution and add a cache.

solve(n):
    if n in cache -> return cache[n]
    result = ... (some recursive work) ...
    cache[n] = result
    return result

Bottom-Up (Tabulation)

Start from the smallest subproblems and work your way up, filling in a table. No recursion at all - just loops.

table[0] = base case
table[1] = base case
for i from 2 to n:
    table[i] = ... (built from earlier table values) ...
return table[n]

Which one to use?

	Top-Down	Bottom-Up
Style	Recursive + cache	Iterative (loops)
Easier to write?	Usually yes - feels natural	Requires knowing the order upfront
Faster?	Slightly slower (function call overhead)	Slightly faster in practice
Risk	Stack overflow for very deep recursion	None
Best for	When only some subproblems are needed	When all subproblems are needed

Both are valid. In interviews, either is accepted. Pick whichever makes more sense to you.

Fibonacci - The Classic DP Example

You’ve probably seen Fibonacci before: each number is the sum of the two before it.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...
fib(n) = fib(n-1) + fib(n-2)

The naive recursive approach:

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

This looks clean but it’s catastrophically slow. Let’s see why.

When you compute fib(5), here’s what happens:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)        <- computed AGAIN
│       ├── fib(1)
│       └── fib(0)    <- computed AGAIN
└── fib(3)            <- computed AGAIN
    ├── fib(2)        <- computed AGAIN
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

fib(3) is computed twice. fib(2) is computed three times. For fib(50), this becomes billions of redundant calls. Time complexity: O(2^n) - exponential and completely unusable for large inputs.

DP Fix - Top-Down (Memoization):

def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]          # already computed - return instantly!
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# fib_memo(50) -> instant. fib_memo(1000) -> instant.
print(fib_memo(50))   # 12586269025

The moment we store results in memo, each value of fib(n) is computed exactly once. The redundant branches disappear entirely.

DP Fix - Bottom-Up (Tabulation):

def fib_dp(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0] = 0   # base case
    dp[1] = 1   # base case

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # build up from small answers

    return dp[n]

print(fib_dp(50))   # 12586269025

We fill the table left to right - each cell uses only the two cells before it. Simple, clean, and fast.

Even better - space-optimized:

Since we only ever look back two steps, we don’t need the whole table:

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

# Time: O(n), Space: O(1) - can't get better than this!
print(fib_optimized(50))   # 12586269025

Approach	Time	Space
Naive recursion	O(2^n)	O(n) stack
Memoization	O(n)	O(n) cache
Tabulation	O(n)	O(n) table
Space-optimized	O(n)	O(1)

0/1 Knapsack - The Most Important DP Problem

The knapsack problem is the most famous DP problem. You’ll encounter it (or variations of it) in almost every DP interview.

The problem: you have a bag with a weight capacity. There are items, each with a weight and a value. You can take each item or leave it (no fractions - that’s what “0/1” means). Maximize the total value you can fit.

Example:

Item	Weight	Value
A	1 kg	$1
B	3 kg	$4
C	4 kg	$5
D	5 kg	$7

Bag capacity: 7 kg

Best choice: take B (3 kg, $4) + C (4 kg,$5) = 7 kg, $9 total.

Why greedy fails here: sorting by value/weight ratio would pick A first ($1/kg), then D ($1.4/kg), then B ($1.33/kg)… This gets complicated and doesn’t guarantee the best answer. We need DP.

The DP idea:

For each item, we have a choice: include it or exclude it. The best answer considering items 1..i with capacity w is:

dp[i][w] = max(
    dp[i-1][w],                          # exclude item i
    dp[i-1][w - weight[i]] + value[i]    # include item i (if it fits)
)

We fill a 2D table where rows are items and columns are capacities.

def knapsack_01(capacity, weights, values):
    n = len(weights)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: don't take item i
            dp[i][w] = dp[i - 1][w]

            # Option 2: take item i (only if it fits)
            if weights[i - 1] <= w:
                value_with_item = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], value_with_item)

    return dp[n][capacity]


weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
capacity = 7
print(knapsack_01(capacity, weights, values))  # Output: 9

Tracing the table for our example (capacity = 7):

      w=0  w=1  w=2  w=3  w=4  w=5  w=6  w=7
i=0:   0    0    0    0    0    0    0    0     <- no items
i=1:   0    1    1    1    1    1    1    1     <- only item A (w=1, v=1)
i=2:   0    1    1    4    5    5    5    5     <- add item B (w=3, v=4)
i=3:   0    1    1    4    5    6    6    9     <- add item C (w=4, v=5)
i=4:   0    1    1    4    5    7    8    9     <- add item D (w=5, v=7)

Answer: dp[4][7] = 9

Each cell says “the best value I can get using items up to row i, with capacity exactly w”. The answer is always in the bottom-right corner.

Recovering which items were taken:

def knapsack_with_items(capacity, weights, values):
    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:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])

    # Trace back to find which items were selected
    chosen = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:   # item i was taken
            chosen.append(i - 1)        # 0-indexed item
            w -= weights[i - 1]

    return dp[n][capacity], chosen[::-1]


max_val, items_taken = knapsack_with_items(7, [1, 3, 4, 5], [1, 4, 5, 7])
print("Max value:", max_val)           # Max value: 9
print("Items taken (0-indexed):", items_taken)  # Items taken: [1, 2] -> B and C

Time complexity: O(n * W) where n is the number of items and W is the capacity. Space complexity: O(n * W) for the table (can be reduced to O(W) with a 1D array).

Note

The 0/1 Knapsack is considered pseudo-polynomial - it looks polynomial but W (capacity) can be huge, making the actual complexity depend on the input value, not just its size. For most interview problems, this is totally fine.

Longest Common Subsequence

The Longest Common Subsequence (LCS) finds the longest sequence of characters that appears in both strings in the same order, but not necessarily side by side.

Example:

String 1: "ABCBDAB"
String 2: "BDCAB"

LCS: "BCAB" or "BDAB" (length 4)

Notice “BCAB” appears in both - in order - even though the characters aren’t all adjacent.

Where is LCS used?

• git diff to show what changed between two file versions
• DNA sequence comparison in bioinformatics
• Spell checkers and autocorrect

The DP recurrence:

If characters match at position i and j: dp[i][j] = dp[i-1][j-1] + 1 If they don’t match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    # dp[i][j] = length of LCS of s1[:i] and s2[:j]
    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]:          # characters match!
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:                                 # characters don't match
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]


print(lcs("ABCBDAB", "BDCAB"))  # Output: 4

Visualizing the table for “ABCB” and “BCB”:

      ""   B    C    B
""  [  0    0    0    0  ]
A   [  0    0    0    0  ]
B   [  0    1    1    1  ]
C   [  0    1    2    2  ]
B   [  0    1    2    3  ]

LCS length = dp[4][3] = 3 -> "BCB"

Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) finds the longest subsequence of a sequence where each element is strictly larger than the one before it.

Example:

Array: [10, 9, 2, 5, 3, 7, 101, 18]
LIS:   [2, 3, 7, 101]  (length 4)
or:    [2, 5, 7, 101]  (length 4)

def lis(nums):
    if not nums:
        return 0

    n = len(nums)
    # dp[i] = length of LIS ending at index i
    dp = [1] * n   # every element is at least a subsequence of length 1

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:    # nums[i] can extend the subsequence ending at j
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)


nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis(nums))   # Output: 4

Time complexity: O(n^2). There’s an O(n log n) solution using binary search, but O(n^2) is easier to understand and fine for most problems.

Coin Change Problem

Given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount.

Example: coins = [1, 5, 6, 9], target = 11

• Greedy would pick 9, then 1, then 1 -> 3 coins
• DP finds: 5 + 6 = 11 -> 2 coins (greedy fails here!)

def coin_change(coins, amount):
    # dp[i] = minimum coins needed to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins needed to make amount 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, 5, 6, 9], 11))   # Output: 2 (5 + 6)
print(coin_change([2], 3))             # Output: -1 (impossible)

Tracing dp for coins=[1,5,6,9], amount=11:

dp[0]  = 0      (base case)
dp[1]  = 1      (use coin 1)
dp[2]  = 2      (1 + 1)
dp[3]  = 3      (1 + 1 + 1)
dp[4]  = 4      (1 + 1 + 1 + 1)
dp[5]  = 1      (use coin 5)
dp[6]  = 1      (use coin 6)
dp[7]  = 2      (1 + 6)
dp[8]  = 2      (2 + 6 or 3 + 5)
dp[9]  = 1      (use coin 9)
dp[10] = 2      (1 + 9 or 5 + 5)
dp[11] = 2      (5 + 6)   <- answer!

Matrix Chain Multiplication

Given a sequence of matrices, find the most efficient order to multiply them. Matrix multiplication is associative - you can group them any way you want - but different groupings have different computational costs.

Why does order matter? Multiplying a 10x30 matrix with a 30x5 matrix then a 5x60 matrix:

• (A _ B) _ C = (10x30 _ 30x5) then (10x5 _ 5x60) = 1500 + 3000 = 4500 operations
• A _ (B _ C) = (30x5 _ 5x60) then (10x30 _ 30x60) = 9000 + 18000 = 27000 operations

Same result, wildly different cost. DP finds the optimal grouping.

def matrix_chain_order(dims):
    # dims[i] and dims[i+1] are the dimensions of matrix i
    n = len(dims) - 1  # number of matrices
    # dp[i][j] = min multiplications to compute matrices i through j
    dp = [[0] * n for _ in range(n)]

    # l = chain length (start from 2 since single matrix costs 0)
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            # Try every possible split point k
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]


# Matrices: 10x30, 30x5, 5x60
dims = [10, 30, 5, 60]
print(matrix_chain_order(dims))  # Output: 4500 (optimal order)

Edit Distance (Levenshtein Distance)

Given two strings, find the minimum number of operations (insert, delete, replace) to convert one into the other.

Example: “kitten” -> “sitting” = 3 operations:

• kitten -> sitten (replace k with s)
• sitten -> sittin (replace e with i)
• sittin -> sitting (insert g at end)

This is used in spell checkers, DNA analysis, and plagiarism detection.

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    # dp[i][j] = min edits to convert word1[:i] to word2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases: converting to/from empty string
    for i in range(m + 1):
        dp[i][0] = i   # delete all characters
    for j in range(n + 1):
        dp[0][j] = j   # insert all characters

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]       # no operation needed
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],       # delete from word1
                    dp[i][j - 1],       # insert into word1
                    dp[i - 1][j - 1]    # replace
                )

    return dp[m][n]


print(edit_distance("kitten", "sitting"))   # Output: 3
print(edit_distance("horse", "ros"))        # Output: 3

How to Approach Any DP Problem

DP problems can feel overwhelming because there’s no single template that fits everything. But there’s a process you can follow every time:

1. Recognize the DP pattern - does the problem ask for min/max of something? Count the number of ways? Does it have overlapping subproblems?

2. Define what dp[i] (or dp[i][j]) means in plain English - write it out as a sentence before coding. This is the most important step.

3. Write the recurrence - how does dp[i] relate to smaller values like dp[i-1]?

4. Identify base cases - what are the smallest inputs you can answer without any recursion?

5. Decide the order - fill bottom-up left to right? Or use memoization top-down?

6. Optimize if needed - can you reduce space by only keeping the last row or last two values?

Tip

Always write the definition of your dp array in a comment before coding. If you can’t state it clearly in English, you don’t fully understand the subproblem yet. “dp[i][j] = the minimum cost to…” - make it concrete.

Common DP Patterns

Most DP problems fall into one of these patterns. Recognizing the pattern instantly narrows down your approach:

Pattern	What it looks like	Example problems
Linear DP	dp depends on previous 1-2 values	Fibonacci, Climbing Stairs
Knapsack	include/exclude choices with a capacity	0/1 Knapsack, Subset Sum
Grid DP	moving through a 2D grid	Unique Paths, Min Path Sum
Interval DP	dp[i][j] over a range	Matrix Chain, Burst Balloons
String DP	comparing/transforming strings	LCS, Edit Distance, Palindromes
Counting DP	count number of ways	Coin Change (ways), Decode Ways

DP vs Greedy vs Recursion

It can be confusing to know which technique to use. Here’s a simple guide:

Situation	Use this
Problem has overlapping subproblems + you need the optimal answer	Dynamic Programming
Local best choice always leads to global best	Greedy
Explore all possibilities, no overlapping subproblems	Recursion / Backtracking
Need to undo choices and try alternatives	Backtracking

Caution

A common mistake: trying a greedy solution when DP is needed. If your greedy gives wrong answers on edge cases, step back and think about whether subproblems overlap. If they do, switch to DP.

Quick Reference

Memoization (Top-Down)

Write recursive solution first. Add a cache dictionary. Before computing, check if the answer is already in the cache. Store the result before returning.

Tabulation (Bottom-Up)

Create a dp array. Fill base cases. Loop from smallest to largest, filling each cell using previously computed cells. Return dp[n] or dp[n][m].

0/1 Knapsack

dp[i][w] = max value using first i items with capacity w. For each item: either skip it (dp[i-1][w]) or take it (dp[i-1][w-wt] + val). Take the max.

Fibonacci / Coin Change

Classic 1D DP. dp[i] depends on dp[i-1] (and maybe dp[i-2]). Fill left to right. Often space-optimizable to O(1) or O(coins).

LCS / Edit Distance

Classic 2D string DP. dp[i][j] compares prefixes of two strings. Match -> extend diagonal. No match -> take best neighbor.

Identify Subproblem First

Before writing any code, define dp[i] in plain English. “dp[i] is the minimum cost to reach step i.” If you can’t say it clearly, slow down and think more.

Summary

The Core Idea

• DP = recursion + memory. Solve each subproblem once and store the result.
• Works when problems have overlapping subproblems and optimal substructure
• Two styles: top-down (memoization with recursion) and bottom-up (tabulation with loops)
• Always define what dp[i] means before writing code
• Most DP solutions can be space-optimized once you understand the pattern

Problems Covered

• Fibonacci - classic intro to memoization vs tabulation; O(2^n) -> O(n) -> O(1) space
• 0/1 Knapsack - take or leave items; 2D dp table; most important DP pattern
• LCS - longest common subsequence; 2D table; used in diff tools and DNA
• LIS - longest increasing subsequence; 1D dp comparing all previous elements
• Coin Change - minimum coins; 1D dp built left to right
• Matrix Chain - optimal parenthesization; interval dp
• Edit Distance - min operations to convert strings; 2D table with insert/delete/replace

Interview Tips

• When you see “minimum”, “maximum”, or “count the number of ways” -> think DP
• Start with brute force recursion, then add memoization - that’s already DP
• Always write dp[i] = ... definition in a comment first
• Draw a small example table by hand before coding 2D DP
• If only the last 1-2 values matter, optimize space with variables instead of array
• Greedy + wrong answer on edge cases? Try DP instead
• Know Fibonacci (1D), Knapsack (2D), and LCS (2D strings) cold - they cover 80% of DP patterns