Dynamic Programming Patterns

Learn the dynamic programming patterns that solve most problems: unbounded knapsack, longest increasing subsequence, interval DP and grid paths in Python.

• Advanced
• 22 min read
• 4 objectives

Before this lessonLesson 9: Dynamic Programming

The Dynamic Programming lesson taught the recipe: define a state, write the transition, set base cases, fill in the right order. It applied it to stairs, coin change, 0/1 knapsack and edit distance. The good news is that most DP problems you will meet are variations on a handful of patterns. Once you recognise the family, the state and transition almost write themselves.

This lesson covers four families: knapsack (choose items under a budget), longest increasing subsequence (best chain in a sequence), interval DP (best way to split a range) and grid DP (paths through a 2D board). For each one we state the dp meaning in one sentence, because that sentence is 80% of the work.

Pattern 1: unbounded knapsack

In 0/1 knapsack each item is used at most once, which is why the earlier lesson looped the capacity downward. If each item can be used any number of times (like buying cloud instances of various sizes), loop the capacity upward: then dp[w - weight] may already include the same item, which is exactly what we want.

dp[w] = the best value achievable with capacity exactly up to w.

def knapsack_01(items, cap):
    dp = [0] * (cap + 1)
    for weight, value in items:
        for w in range(cap, weight - 1, -1):     # downward: each item once
            dp[w] = max(dp[w], dp[w - weight] + value)
    return dp[cap]

def knapsack_unbounded(items, cap):
    dp = [0] * (cap + 1)
    for weight, value in items:
        for w in range(weight, cap + 1):         # upward: reuse allowed
            dp[w] = max(dp[w], dp[w - weight] + value)
    return dp[cap]

servers = [(3, 50), (4, 70), (5, 80)]     # (cpu units, requests per sec)
print(knapsack_01(servers, 10), knapsack_unbounded(servers, 10))

150 170

With a 10-unit budget, 0/1 can only pick distinct servers (4 + 5 gives 150), while unbounded can take the 3-unit and 4-unit servers more than once (3 + 3 + 4 gives 170). Both are O(n * cap) time and O(cap) space. The same table, with + instead of max, counts combinations, as in "how many ways to make change".

def count_ways(coins, amount):
    dp = [1] + [0] * amount          # one way to make 0: take nothing
    for c in coins:                  # coins outer loop = combinations
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

print(count_ways([1, 2, 5], 5), count_ways([2, 5, 3, 6], 10))

4 5

Pattern 2: longest increasing subsequence

Given daily active users over time, what is the longest stretch of days (not necessarily consecutive) where the numbers strictly grow? A subsequence keeps order but may skip elements. dp[i] = the length of the longest increasing subsequence that ends at index i. To compute it, look at every earlier j with a smaller value and extend the best one.

def lis_quadratic(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

users = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_quadratic(users))

4

That is O(n²). A cleverer version keeps tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. That list is always sorted, so each new number finds its place with binary search: it either extends the longest run or replaces a tail with something smaller (keeping future options open).

# from earlier in this lesson
users = [10, 9, 2, 5, 3, 7, 101, 18]

# new code
from bisect import bisect_left

def lis_fast(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)          # extends the longest subsequence
        else:
            tails[i] = x             # better (smaller) tail for length i+1
    return len(tails)

print(lis_fast(users))
print(lis_fast([3, 3, 3]), lis_fast(list(range(1000))))

4
1 1000

Time O(n log n), space O(n). Note that tails is not itself a valid subsequence; only its length is meaningful. Use bisect_right instead if you want non-decreasing (allowing equal values). Many problems reduce to LIS: stacking boxes, nesting envelopes (sort by one dimension, LIS on the other) and scheduling chains.

Pattern 3: interval DP

Some problems ask for the best way to process a range [i, j], where the answer depends on how you split it. dp[i][j] = the answer for the sub-range from i to j. You fill it by increasing length, so shorter ranges are ready when longer ones need them. The classic example is the longest palindromic subsequence: the characters you can keep (in order) that read the same backwards.

def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1                          # length-1 ranges
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

for word in ["bbbab", "stackcone", "racecar"]:
    print(word, longest_palindrome_subseq(word))

bbbab 4
stackcone 3
racecar 7

Time O(n²), space O(n²). Harder interval problems (matrix chain multiplication, burst balloons, optimal merge of files) add an inner loop over a split point k in [i, j], making them O(n³). Here is merging adjacent files where each merge costs the combined size:

from itertools import accumulate

def min_merge_cost(sizes):
    n = len(sizes)
    prefix = [0] + list(accumulate(sizes))
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = min(dp[i][k] + dp[k + 1][j] for k in range(i, j))
            dp[i][j] += prefix[j + 1] - prefix[i]    # cost of the final merge
    return dp[0][n - 1]

print(min_merge_cost([40, 10, 30, 20]))

200

Pattern 4: grid DP

A robot moves only right or down across a grid; how many routes reach the bottom-right corner, or what is the cheapest one? dp[r][c] = the answer for reaching cell (r, c). Each cell depends only on the cell above and the cell to the left.

def min_path_cost(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                dp[r][c] = grid[0][0]
            else:
                up = dp[r - 1][c] if r > 0 else float("inf")
                left = dp[r][c - 1] if c > 0 else float("inf")
                dp[r][c] = grid[r][c] + min(up, left)
    return dp[-1][-1]

costs = [[1, 3, 1],
         [1, 5, 1],
         [4, 2, 1]]
print(min_path_cost(costs))

7

Because each row only needs the previous row, you can keep a single 1D list and update it in place. That drops space from O(rows * cols) to O(cols), a trick that applies to most 2D DP tables, including LCS and edit distance.

def unique_paths(grid):
    # grid of "." (open) and "#" (blocked); count right/down paths
    cols = len(grid[0])
    row = [0] * cols
    row[0] = 1
    for line in grid:
        for c in range(cols):
            if line[c] == "#":
                row[c] = 0
            elif c > 0:
                row[c] += row[c - 1]      # row[c] still holds the value from above
    return row[-1]

print(unique_paths(["...", "...", "..."]))
print(unique_paths(["...", ".#.", "..."]))

6
2

Time O(rows * cols), space O(cols).

How to recognise the pattern

• "Choose items with a weight/cost limit" or "make an amount": knapsack. Can items repeat? Loop upward.
• "Longest / best chain in order", "subsequence": LIS-style, dp[i] ends at i.
• "Best way to split, merge or remove from a range", "palindrome": interval DP, fill by length.
• "Paths on a board moving right/down": grid DP, often reducible to one row.
• Two strings compared position by position: the 2D table from LCS and edit distance.

Recap

• Most DP problems belong to a few families; naming the family gives you the state.
• 0/1 knapsack loops capacity downward, unbounded loops upward; outer loop choice decides combinations vs permutations.
• LIS is O(n²) with a simple table and O(n log n) with a sorted tails list and bisect.
• Interval DP fills dp[i][j] by increasing length, often with a split point k.
• Grid DP depends on up and left cells, so one rolling row is usually enough.

# Write your solution here