Dynamic Programming: From Scary to Systematic in One Post

Why DP Has a Reputation Problem

Dynamic programming has the worst reputation of any topic in interview prep. Candidates describe it as "magic," "pattern-matching from memory," or "the one topic where you either see it or you don't." None of that is true — it just reflects the way DP is usually taught.

Most tutorials teach DP by example: here is the Fibonacci solution, here is the coin change solution, here is the longest common subsequence solution. Memorize these, recognize similar problems, adapt the code. This produces candidates who can solve problems they've seen before and are helpless in front of anything new.

The right way to learn DP is to understand why it works, which makes the how systematic rather than intuitive. This post teaches DP that way.

The Two Prerequisites for DP

A problem is solvable with dynamic programming if and only if it has two properties:

Property 1 — Optimal Substructure: The optimal solution to the problem can be constructed from the optimal solutions of its subproblems.

Example: The shortest path from A to C passing through B is the shortest path from A to B plus the shortest path from B to C. If you had a non-shortest path from A to B, you could improve the overall solution by swapping it. This is optimal substructure.

Counter-example: The longest path in a graph does NOT have optimal substructure. The longest path from A to C is not necessarily the longest path from A to B plus the longest path from B to C — those two subpaths might share nodes and create a cycle.

Property 2 — Overlapping Subproblems: The recursive solution solves the same subproblems multiple times.

Example: Computing fib(5) requires fib(3) twice and fib(2) three times. Without memoization, the same work is repeated exponentially. DP stores results and reuses them.

The diagnostic test: Draw the recursion tree for your recursive solution. If you see the same subproblem node appearing more than once, you have overlapping subproblems. If the overall answer is a combination of optimal subproblem answers, you have optimal substructure. Both present → use DP.

Top-Down vs Bottom-Up: Two Sides of the Same Coin

Every DP solution can be written in two equivalent ways.

Top-Down (Memoization): Write the natural recursion, add a cache. The cache intercepts repeated subproblem calls and returns the stored result instantly.

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

# Cleaner with functools:
from functools import lru_cache

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

Bottom-Up (Tabulation): Identify the subproblem order (smallest to largest), fill a table in that order. No recursion, no call stack overhead.

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]
    return dp[n]

# Space-optimized (when only last k values needed):
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

Which to use in interviews?

Recommendation: When you don't immediately see the DP structure, start with top-down (write the recursion, add @lru_cache). Once it works, convert to bottom-up if needed for space optimization.

The 6 DP Patterns

All DP interview problems fall into one of six patterns. Each pattern has a characteristic subproblem definition and recurrence structure.

Pattern 1: 1D DP — Linear Sequence

When: The problem involves a single sequence (array, string) and decisions at each position depend on previous positions.

Subproblem: dp[i] = answer for the first i elements (or ending at index i).

# Climbing Stairs: how many ways to climb n stairs (1 or 2 steps at a time)?
def climb_stairs(n):
    if n <= 2: return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]    # came from i-1 or i-2
    return dp[n]

# House Robber: max sum with no two adjacent elements
def rob(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1],            # skip nums[i]
                    dp[i-2] + nums[i])  # take nums[i]
    return dp[-1]
    # Space-optimized: two variables instead of array

# Maximum Subarray (Kadane's Algorithm)
def max_subarray(nums):
    # dp[i] = maximum subarray sum ENDING at index i
    dp = nums[0]
    result = nums[0]
    for num in nums[1:]:
        dp = max(num, dp + num)   # start fresh or extend
        result = max(result, dp)
    return result

Recurrence pattern: dp[i] = f(dp[i-1], dp[i-2], ..., nums[i])

Pattern 2: 2D DP — Grid / Two Sequences

When: The problem involves a 2D grid, or two sequences being compared/combined.

Subproblem: dp[i][j] = answer for the first i rows and j columns (or first i elements of seq1 and j elements of seq2).

# Unique Paths: count paths from top-left to bottom-right (only right/down moves)
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]   # came from above or left
    return dp[m-1][n-1]

# Minimum Path Sum: minimum sum path from top-left to bottom-right
def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n):   dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):   dp[i][0] = dp[i-1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

# Edit Distance: minimum operations to convert word1 to word2
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)]
    for i in range(m+1): dp[i][0] = i   # delete all of word1
    for j in range(n+1): dp[0][j] = j   # insert all of word2

    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]

Pattern 3: Knapsack — Include/Exclude Decisions

When: You have a set of items, each with a weight and value. You must decide to include or exclude each item subject to a capacity constraint.

Subproblem: dp[i][w] = maximum value using first i items with capacity w.

# 0/1 Knapsack: each item can be used at most once
def knapsack_01(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]   # exclude item i
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])  # include
    return dp[n][capacity]

# Space-optimized to 1D (iterate capacity in reverse to avoid using item twice):
def knapsack_01_opt(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):   # reverse!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

# Coin Change (Unbounded Knapsack): minimum coins to make amount
# Each coin can be used unlimited times → forward iteration, not reverse
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for w in range(coin, amount + 1):   # forward: allows reuse
            dp[w] = min(dp[w], dp[w - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# Coin Change 2: number of ways to make amount (not minimum coins)
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    return dp[amount]

The 0/1 vs Unbounded distinction:

• 0/1 Knapsack (each item once) → iterate capacity backward in 1D optimization

• Unbounded Knapsack (items reusable) → iterate capacity forward

This single distinction resolves most knapsack confusion.

Pattern 4: LCS / LIS — Longest Subsequence

When: The problem asks for the longest subsequence satisfying a condition. The "longest common subsequence" family includes LCS, LIS, and many string DP problems.

# Longest Common Subsequence
def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1        # characters match: extend
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one character
    return dp[m][n]

# Longest Increasing Subsequence — O(n²) DP
def lis_dp(nums):
    n = len(nums)
    dp = [1] * n   # dp[i] = length of LIS ending at index i
    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)

# Longest Increasing Subsequence — O(n log n) with patience sorting
def lis_fast(nums):
    tails = []   # tails[i] = smallest tail of all LIS of length i+1
    for num in nums:
        lo, hi = 0, len(tails)
        while lo < hi:
            mid = (lo + hi) // 2
            if tails[mid] < num: lo = mid + 1
            else: hi = mid
        if lo == len(tails):
            tails.append(num)
        else:
            tails[lo] = num
    return len(tails)

# Longest Palindromic Subsequence
def lps(s):
    # LPS(s) = LCS(s, reversed(s))
    return lcs(s, s[::-1])

Pattern 5: Interval DP — Splitting a Range

When: The problem involves splitting a sequence at some position and combining results from both halves. The answer depends on how you split.

Subproblem: dp[i][j] = answer for the subarray/substring from index i to j.

Fill order: By interval length (length 1 first, then 2, then 3...).

# Matrix Chain Multiplication: minimum operations to multiply a chain of matrices
def matrix_chain(dims):
    n = len(dims) - 1    # number of matrices
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):        # interval length
        for i in range(n - length + 1):   # interval start
            j = i + length - 1            # interval end
            dp[i][j] = float('inf')
            for k in range(i, j):         # split point
                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]

# Burst Balloons: maximum coins from bursting balloons optimally
def max_coins(nums):
    nums = [1] + nums + [1]   # add boundary balloons
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):
        for left in range(0, n - length):
            right = left + length
            for k in range(left + 1, right):   # k = last balloon to burst in [left, right]
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k] + nums[left] * nums[k] * nums[right] + dp[k][right]
                )
    return dp[0][n-1]

# Palindromic Substrings: count all palindromic substrings
def count_substrings(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length <= 2 or dp[i+1][j-1]):
                dp[i][j] = True
                count += 1
    return count

Pattern 6: State Machine DP

When: The problem has distinct modes or states, and transitions between states have costs. Common in stock trading, finite automata, and game problems.

Subproblem: dp[i][state] = best value at index i while in state.

# Best Time to Buy and Sell Stock with Cooldown
def max_profit_cooldown(prices):
    # States: HELD (holding stock), SOLD (just sold, in cooldown), REST (can buy)
    held = -float('inf')
    sold = 0
    rest = 0

    for price in prices:
        prev_held, prev_sold, prev_rest = held, sold, rest
        held = max(prev_held, prev_rest - price)   # hold or buy
        sold = prev_held + price                   # sell what was held
        rest = max(prev_rest, prev_sold)            # rest or come out of cooldown
    return max(sold, rest)

# Best Time to Buy and Sell Stock with Transaction Fee
def max_profit_fee(prices, fee):
    held = -float('inf')
    cash = 0
    for price in prices:
        held = max(held, cash - price)             # hold or buy
        cash = max(cash, held + price - fee)        # keep cash or sell (minus fee)
    return cash

# Best Time to Buy and Sell Stock — at most k transactions
def max_profit_k(k, prices):
    n = len(prices)
    if not prices or k == 0: return 0
    if k >= n // 2:   # unlimited transactions effectively
        return sum(max(0, prices[i] - prices[i-1]) for i in range(1, n))

    # dp[t][0] = max profit with t transactions, not holding
    # dp[t][1] = max profit with t transactions, holding
    dp = [[-float('inf'), -float('inf')] for _ in range(k+1)]
    dp[0][0] = 0

    for price in prices:
        for t in range(k, 0, -1):
            dp[t][0] = max(dp[t][0], dp[t][1] + price)      # sell
            dp[t][1] = max(dp[t][1], dp[t-1][0] - price)    # buy
    return max(dp[t][0] for t in range(k+1))

The DP Problem-Solving Process

When facing an unknown DP problem in an interview, follow this sequence:

Step 1 — Verify DP applies. Ask: "Does the optimal answer depend on optimal sub-answers?" If yes, you likely have optimal substructure. Draw the recursion tree — do subproblems repeat? If yes, DP is appropriate.

Step 2 — Define the subproblem. State explicitly: "Let dp[i] be..." or "Let dp[i][j] be..." The definition must be complete — you should be able to answer any subproblem instance just from its indices.

Step 3 — Write the recurrence. How does dp[i] relate to smaller subproblems? Consider all choices at position i and take the best.

Step 4 — Identify base cases. What are the smallest subproblems whose answers are known without recursion?

Step 5 — Determine fill order. For bottom-up: which subproblems must be solved before others? (Usually left-to-right for 1D, top-left to bottom-right for 2D, small-to-large length for intervals.)

Step 6 — Optimize space. Does the recurrence only use the last row? Last two values? If so, reduce from O(n²) to O(n) or O(1).

IDENTIFY PATTERN:
  Single sequence with choices at each index    → Pattern 1: 1D DP
  Two sequences or 2D grid                      → Pattern 2: 2D DP
  Include/exclude items with capacity           → Pattern 3: Knapsack
  Longest subsequence satisfying condition      → Pattern 4: LCS/LIS
  Optimal way to split a range                  → Pattern 5: Interval DP
  Problem with distinct modes/states            → Pattern 6: State Machine

The 10 Must-Know Problems

Work through 1–4 first to build confidence with the mechanics. Problem 5 (Edit Distance) is the canonical 2D DP — understand it deeply. Problem 6 covers both 0/1 and unbounded knapsack variants. Problems 7–8 together cover the LCS/LIS family. Problems 9–10 are the hardest conceptual jumps — interval DP and state machine DP respectively.

Bottom Line

DP is not about recognizing which template to apply. It is about recognizing two structural properties — optimal substructure and overlapping subproblems — and then systematically defining a subproblem, writing a recurrence, and filling a table.

The six patterns in this post cover every DP problem that appears in interviews. Not because interviews are limited, but because all DP problems have the same underlying structure — they only differ in how the subproblem is indexed and how the recurrence relates adjacent indices.

Write the recurrence before writing any code. State the subproblem definition out loud. Draw the table for a small example. The code is the last step, not the first.

🧭 What's Next in Chapter 3

• Post 13: Greedy Algorithms — easy to implement, hard to justify; learn the exchange argument and the 5 patterns that tell you when being selfish gives the optimal answer