Lesson 16 of 16 Dynamic Programming

Dynamic Programming Patterns (1D and 2D)

Dynamic programming via state, recurrence and fill order: climbing stairs, house robber, coin change, LIS, LCS and edit distance in Python.

55-70 min advanced 0/16 lessons done
Course contents Lesson 16 of 16 · 0 done
On this page (9 sections)
  1. What you will learn
  2. Signals
  3. The recipe
  4. Code
  5. Top-down or bottom-up?
  6. DP families worth recognising
  7. Key takeaways
  8. Exercises
  9. Quiz

What you will learn

  • A four-step recipe for any DP problem.
  • 1D DP with O(1) space, and when 2D tables are needed.
  • Top-down memoisation versus bottom-up tables.

Signals

  • “Number of ways”, “minimum/maximum cost”, “longest/shortest”, “is it possible”.
  • Choices at each step, where brute force recursion recomputes the same subproblems.
  • Greedy looks tempting but has counterexamples.

The recipe

  1. State: what does dp[i] (or dp[i][j]) mean, in words?
  2. Recurrence: how is it built from smaller states?
  3. Base cases: the smallest states you know directly.
  4. Order and answer: fill in an order where dependencies are ready; say which cell holds the answer.

Writing step 1 as a sentence (“dp[a] = fewest coins that make amount a”) is the most valuable habit in DP.

Code

"""Dynamic programming: 1D (climbing stairs, house robber, coin change, LIS) and 2D (LCS, edit distance)."""
from bisect import bisect_left
from functools import lru_cache


def climb_stairs(n):
    a, b = 1, 1  # ways to reach step i-1 and step i
    for _ in range(n - 1):
        a, b = b, a + b
    return b


def rob(houses):
    take, skip = 0, 0  # best total if we rob / don't rob the previous house
    for h in houses:
        take, skip = skip + h, max(take, skip)
    return max(take, skip)


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


def lis_length(nums):
    tails = []  # tails[k] = smallest tail of an increasing subsequence of length k+1
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)


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


def edit_distance(a, b):
    @lru_cache(maxsize=None)  # top-down memoisation of the same recurrence
    def go(i, j):
        if i == len(a):
            return len(b) - j
        if j == len(b):
            return len(a) - i
        if a[i] == b[j]:
            return go(i + 1, j + 1)
        return 1 + min(go(i + 1, j),      # delete a[i]
                       go(i, j + 1),      # insert b[j]
                       go(i + 1, j + 1))  # replace
    return go(0, 0)


if __name__ == "__main__":
    print([climb_stairs(n) for n in range(1, 8)])
    print(rob([2, 7, 9, 3, 1]), coin_change([1, 2, 5], 11), coin_change([2], 3))
    print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))
    print(lcs("abcde", "ace"), edit_distance("horse", "ros"), edit_distance("intention", "execution"))

Output:

[1, 2, 3, 5, 8, 13, 21]
12 3 -1
4
3 3 5
  • Climbing stairs: ways(n) = ways(n−1) + ways(n−2). Only the last two values are needed, so O(1) space.
  • House robber: for each house, either rob it (previous house skipped) or skip it. Two variables replace the table. Best for [2, 7, 9, 3, 1] is 2 + 9 + 1 = 12.
  • Coin change: dp[a] = 1 + min(dp[a − c]). Greedy fails for some coin sets; DP doesn’t. Amount 11 with 5 needs 3 coins; 3 with 2 is impossible.
  • Longest increasing subsequence: the O(n²) DP is dp[i] = 1 + max(dp[j]) over smaller earlier values; the code shows the O(n log n) “tails + binary search” version.
  • LCS (2D): dp[i][j] = LCS of the first i characters of a and first j of b. Match → diagonal + 1; otherwise the max of dropping one character.
  • Edit distance (top-down): the same kind of 2D recurrence written as a memoised recursion: delete, insert or replace when characters differ.

Top-down or bottom-up?

  • Top-down (recursion + lru_cache): closest to the recurrence, computes only states you need. Watch recursion depth.
  • Bottom-up (tables): no recursion limit, easy space optimisation (keep only the previous row).

Start top-down to get it right, then convert if needed.

DP families worth recognising

FamilyExamples
Linear (1D)Stairs, house robber, decode ways, word break
KnapsackCoin change, partition equal subset sum, target sum
SubsequenceLIS, LCS, edit distance, distinct subsequences
GridUnique paths, minimum path sum
IntervalBurst balloons, palindrome partitioning
BitmaskTravelling salesman for small n

Practise: 1D DP, 2D DP and bitmask DP problems. For full problem lists, work through the Blind 75, LeetCode 150 and the DSA master sheet, naming the pattern before you code each one.

Key takeaways

  • Define the state in words first, then the recurrence, base cases and fill order.
  • Reduce space when each state depends only on a few previous ones.
  • Memoised recursion and bottom-up tables are the same DP; pick what’s clearer, then optimise.
  • Learn the families (knapsack, subsequence, grid, interval) to spot DP quickly.

Exercises

  1. Word break: can a string be split into dictionary words?
  2. Partition equal subset sum with a 1D boolean knapsack array.
  3. Rewrite edit_distance bottom-up with only two rows of memory.

Quiz

  1. What is the state in coin change, in words?
  2. Why can house robber use two variables instead of an array?
  3. In LCS, what happens when a[i-1] == b[j-1]?
Show answers
  1. dp[a] is the fewest coins that add up to amount a (or infinity if impossible).
  2. Each state depends only on the previous one or two states, so older values are never needed again.
  3. Both characters extend a common subsequence: dp[i][j] = dp[i-1][j-1] + 1.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).