DP Patterns: Defining the State, Choosing Loop Order, and Recognizing Knapsack, LCS, and LIS
Key takeaways
Most DP problems reuse a handful of state shapes: a prefix, a grid, two string prefixes, a capacity. Recognizing the shape is half the work; the other half is the details that decide correctness, such as loop direction in knapsack and loop order in counting problems.
Introduction
Most DP problems are variations of a few patterns. Knowing the patterns does not make new problems easy, but it does give you a short list of state shapes to try first.
Every DP solution is built from the same three decisions, and the patterns below are really just common answers to them:
- State: what does
dp[i](ordp[i][j]) mean, in one precise sentence? “The number of ways to reach step i.” “The best value using the first i items with capacity w.” If you cannot state it in a sentence, the recurrence will be wrong. - Transition: how is one state computed from smaller ones? This usually comes from asking “what was the last decision?” (last step was 1 or 2 stairs; last item was taken or not; last characters matched or not).
- Order and base cases: in what order must states be filled so that every state’s inputs are ready, and what are the smallest states whose values you know directly?
Wrong DP solutions almost always fail at the first decision, not the code. A vague state like “dp[i] is the answer for i” leaves it unclear whether the i-th element is included or merely available, and those two readings produce different recurrences. The LIS section below is a good example: dp[i] there means “the longest increasing subsequence that ends at index i”, and that “ends at” is what makes the recurrence possible.
1D DP Patterns
In 1D DP, dp[i] typically means “optimal value from first to ith element” or “optimal value for subproblem of size i”. The two examples below are representative patterns that fill the next cell using only previous cells.
Pattern 1: Using Previous Values
def climb_stairs(n):
"""
Climbing stairs (1 or 2 steps)
dp[i] = dp[i-1] + dp[i-2]
"""
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]
return dp[n]
print(climb_stairs(5)) # 8Pattern 2: Max/Min Selection
def rob(houses):
"""
House Robber (cannot rob adjacent houses)
dp[i] = max(dp[i-1], dp[i-2] + houses[i])
"""
if not houses:
return 0
if len(houses) == 1:
return houses[0]
dp = [0] * len(houses)
dp[0] = houses[0]
dp[1] = max(houses[0], houses[1])
for i in range(2, len(houses)):
dp[i] = max(dp[i-1], dp[i-2] + houses[i])
return dp[-1]
# Test
print(rob([2, 7, 9, 3, 1])) # 12 (2+9+1)Both examples only look back one or two steps, so the full array is unnecessary: two variables (prev2, prev1) are enough, reducing memory from O(n) to O(1). Keep the array while you develop and debug a solution, though, because printing dp is the easiest way to check the recurrence by hand on a small input. Optimize the space only after the answers are right.
Note that House Robber’s state is “the best total using houses 0..i, whether or not house i is robbed”. That is why dp[i-1] is a valid option: skipping house i simply carries over the previous best. An alternative state, “the best total ending with robbing house i”, also works but needs a different recurrence (houses[i] + max(dp[0..i-2])). Neither is wrong, but mixing the two meanings in one solution is a classic bug.
2D DP Patterns
Pattern 1: Grid Paths
def unique_paths(m, n):
"""
Number of paths in m×n grid
dp[i][j] = dp[i-1][j] + dp[i][j-1]
"""
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]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28Pattern 2: LCS (Longest Common Subsequence)
def lcs(s1, s2):
"""
Longest Common Subsequence
"ABCDGH", "AEDFHR" → "ADH" (length 3)
"""
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]
# Test
print(lcs("ABCDGH", "AEDFHR")) # 3LCS Backtracking:
def lcs_with_string(s1, s2):
"""
Return LCS string, not just length
"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Build DP table
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])
# Backtrack to find string
result = []
i, j = m, n
while i > 0 and j > 0:
if s1[i-1] == s2[j-1]:
result.append(s1[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
# Test
print(lcs_with_string("ABCDGH", "AEDFHR")) # "ADH"The LCS table uses one extra row and column: dp[i][j] is the LCS length of the first i characters of s1 and the first j characters of s2, so dp[0][*] and dp[*][0] represent empty prefixes and are 0. This “prefix length” convention removes all special cases at the edges, which is why s1[i-1] appears in the code. The same convention appears in edit distance below, and it is worth adopting as a default for any DP over two sequences.
The reconstruction step walks back from dp[m][n] and retraces which choice produced each value. That only works because the whole table is kept. If you reduce LCS to two rows to save memory, you can still compute the length but can no longer recover the string (without more advanced techniques such as Hirschberg’s algorithm). When a problem asks for the actual sequence, not just its length, plan for the full table. Also, when there are several LCSs of the same length, the tie-breaking in the elif decides which one you get. Tests that compare against one specific string can fail even though the answer is valid.
Knapsack Problem Patterns
0-1 Knapsack
def knapsack_01(weights, values, capacity):
"""
Each item 0 or 1 time
"""
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):
# Don't take
dp[i][w] = dp[i-1][w]
# Take
if weights[i-1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]
)
return dp[n][capacity]
# Test
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_01(weights, values, capacity)) # 10Space Optimized (1D):
def knapsack_01_optimized(weights, values, capacity):
"""
O(capacity) space
"""
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# Iterate backwards to prevent overwriting
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]The backward loop is the entire difference between 0-1 knapsack and unbounded knapsack, and it is the most commonly misunderstood line in DP code. In the 1D version, dp[w] holds values from the previous item’s row until it is overwritten. The update reads dp[w - weights[i]], a smaller index. If w goes from high to low, that smaller index has not been updated yet for item i, so it still means “best without item i”, and item i is used at most once. If w went from low to high, dp[w - weights[i]] might already include item i, and adding it again would use the same item twice. Loop direction is literally how the code encodes “each item once”.
Keep in mind that knapsack DP is O(n × capacity). That is pseudo-polynomial: fast when capacity is a small integer, but useless when weights are large (a capacity of 10⁹) or not integers. In those cases, the problem needs a different approach, such as DP over values instead of weights, meet-in-the-middle, or an approximation.
Unbounded Knapsack
def knapsack_unbounded(weights, values, capacity):
"""
Each item unlimited times
"""
dp = [0] * (capacity + 1)
for w in range(capacity + 1):
for i in range(len(weights)):
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# Test
weights = [1, 3, 4]
values = [15, 50, 60]
capacity = 8
print(knapsack_unbounded(weights, values, capacity)) # 130 (3+3+1+1 → 50+50+15+15)Here the forward direction is exactly what you want: dp[w - weights[i]] may already include item i, which is allowed because items can repeat.
Loop order in counting problems: combinations vs permutations
For maximizing a value, the order of the two loops in unbounded knapsack does not matter. For counting ways, it changes the answer:
def count_combinations(coins, amount):
# coins in the OUTER loop: each multiset counted once
dp = [1] + [0] * amount
for c in coins:
for a in range(c, amount + 1):
dp[a] += dp[a - c]
return dp[amount]
def count_permutations(coins, amount):
# amount in the OUTER loop: every ordering counted separately
dp = [1] + [0] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] += dp[a - c]
return dp[amount]
print(count_combinations([1, 2], 3)) # 2: {1,1,1}, {1,2}
print(count_permutations([1, 2], 3)) # 3: 1+1+1, 1+2, 2+1With coins in the outer loop, coins are added in a fixed order, so 1+2 and 2+1 are built only one way. With the amount in the outer loop, every coin can be the “last” one at every step, so each ordering is counted. LeetCode 518 (Coin Change II) wants the first; LeetCode 377 (Combination Sum IV) wants the second. The two solutions differ only in which loop is outside.
This is the DP bug I find most instructive, because both versions look equally reasonable, both pass the problem’s small examples if the example has only one arrangement, and the difference only shows up on inputs where order could matter. When I write a counting DP, I now ask explicitly whether 1+2 and 2+1 are the same answer, before choosing the loop order.
LIS (Longest Increasing Subsequence)
O(n²) Solution
def lis_n2(arr):
"""
Longest Increasing Subsequence
[10, 9, 2, 5, 3, 7, 101, 18] → 4 ([2,3,7,18])
"""
n = len(arr)
dp = [1] * n
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)
# Test
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_n2(arr)) # 4O(n log n) Solution
import bisect
def lis_nlogn(arr):
"""
Using binary search
"""
dp = []
for num in arr:
pos = bisect.bisect_left(dp, num)
if pos == len(dp):
dp.append(num)
else:
dp[pos] = num
return len(dp)
# Test
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_nlogn(arr)) # 4How O(n log n) Works:
arr = [10, 9, 2, 5, 3, 7, 101, 18]
Step 1: num=10, dp=[10]
Step 2: num=9, dp=[9] (replace 10)
Step 3: num=2, dp=[2] (replace 9)
Step 4: num=5, dp=[2,5] (append)
Step 5: num=3, dp=[2,3] (replace 5)
Step 6: num=7, dp=[2,3,7] (append)
Step 7: num=101,dp=[2,3,7,101] (append)
Step 8: num=18, dp=[2,3,7,18] (replace 101)
Length = 4The array in the O(n log n) version is usually named dp, but it has a different meaning from the O(n²) table: tails[k] is the smallest possible last element of any increasing subsequence of length k + 1 seen so far. Keeping tails as small as possible leaves the most room for future elements to extend them. Because the array is always sorted, binary search finds where each new number belongs.
A common misconception is that this array is the longest increasing subsequence. It is not. Its length is correct, but its contents mix elements from different subsequences. For [3, 4, 1], it ends as [1, 4], which is not a subsequence of the input at all (1 comes after 4). To reconstruct an actual LIS, also store, for each element, the index of its predecessor at the moment it was placed, and walk back from the last element. And note the choice of bisect_left: it gives a strictly increasing subsequence. Using bisect_right instead gives the longest non-decreasing one, which is a different problem that shows up in variants such as “minimum removals to make an array sorted”.
Edit Distance Pattern
def edit_distance(s1, s2):
"""
Minimum operations to convert s1 to s2
Operations: insert, delete, replace
"horse", "ros" → 3
(replace h→r, delete o, delete e)
"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initial values
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Fill table
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]
else:
dp[i][j] = min(
dp[i-1][j] + 1, # delete
dp[i][j-1] + 1, # insert
dp[i-1][j-1] + 1 # replace
)
return dp[m][n]
# Test
print(edit_distance("horse", "ros")) # 3The three options in the min correspond to the three operations, and it helps to read them as prefix changes. dp[i-1][j] + 1: delete s1[i-1], then convert the rest. dp[i][j-1] + 1: convert s1[:i] into s2[:j-1], then insert s2[j-1]. dp[i-1][j-1] + 1: replace one character with the other. The base cases say that converting a prefix of length i to the empty string takes i deletions, and the reverse takes j insertions. This is the Levenshtein distance, used in spell checkers, fuzzy search, and DNA alignment, often with different costs per operation, which only changes the + 1 terms.
Recognizing and Debugging DP
From problem statement to pattern
A few phrases in a problem statement point strongly to a pattern. “Number of ways” or “minimum cost to reach” position n: 1D DP over positions. “Two strings” or “two sequences”: a 2D table over prefixes (LCS, edit distance). “Capacity”, “budget”, or “exact sum” with items: knapsack. “Longest increasing” or “chain” of pairs: LIS. When the problem involves a choice that depends on what you did before (holding a stock, cooldown), add that as an extra state dimension, which is the state machine pattern in section 7.
It is also worth checking whether DP is needed at all. If choosing the locally best option at each step can be proven optimal, a greedy algorithm is simpler and faster (see Greedy). The classic counterexample is coin change with coins {1, 3, 4} and amount 6: greedy takes 4+1+1 (3 coins), DP finds 3+3 (2 coins).
Debugging a wrong DP
When a DP gives wrong answers, print the table for the smallest failing input and fill a few cells by hand, using the one-sentence meaning of the state. The first cell where your hand calculation and the table disagree points to the bug, which is almost always a base case, an off-by-one in the prefix convention, or a loop that runs in the wrong direction. Comparing against a brute-force solution on random small inputs finds these quickly, and is how I would test any DP before trusting it on large inputs.
Common Mistakes
# ❌ Wrong: Forgot initial values
dp = [0] * n
# dp[0], dp[1] not set!
# ✅ Correct: Set initial values
dp = [0] * n
dp[0] = 1
dp[1] = 1
# ❌ Wrong: Index out of bounds
for i in range(n):
dp[i] = dp[i-1] + dp[i-2] # i=0, i=1 error!
# ✅ Correct: Start from valid index
for i in range(2, n):
dp[i] = dp[i-1] + dp[i-2]Advanced Patterns
Partition DP
def word_break(s, word_dict):
"""
Check if string can be segmented into dictionary words
s = "leetcode", wordDict = ["leet", "code"] → True
"""
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_dict:
dp[i] = True
break
return dp[n]
# Test
s = "leetcode"
word_dict = {"leet", "code"}
print(word_break(s, word_dict)) # TrueState Machine DP
def max_profit_cooldown(prices):
"""
Stock trading with cooldown
States: hold, sold, rest
"""
if not prices:
return 0
n = len(prices)
hold = [0] * n
sold = [0] * n
rest = [0] * n
hold[0] = -prices[0]
for i in range(1, n):
hold[i] = max(hold[i-1], rest[i-1] - prices[i])
sold[i] = hold[i-1] + prices[i]
rest[i] = max(rest[i-1], sold[i-1])
return max(sold[-1], rest[-1])
# Test
prices = [1, 2, 3, 0, 2]
print(max_profit_cooldown(prices)) # 3word_break shows partition DP: dp[i] is True when the first i characters can be split into words, and the transition tries every possible last word s[j:i]. It is O(n²) substring checks. Limiting j to the length of the longest dictionary word makes it much faster in practice.
The stock problem shows why an extra state dimension is often the cleanest way to handle rules: instead of one dp[i], keep one value per situation you can be in on day i (holding a share, just sold, resting). Each rule of the problem becomes a transition between situations: you can only buy from rest (which enforces the cooldown), and you can only sell from hold. Drawing the three states with arrows before writing code makes the recurrences almost mechanical.
Matching a problem to a DP pattern
| Pattern | Recurrence | Example |
|---|---|---|
| 1D Previous | dp[i] = f(dp[i-1]) | Climbing stairs |
| 1D Max/Min | dp[i] = max(...) | House robber |
| 2D Grid | dp[i][j] = f(dp[i-1][j], dp[i][j-1]) | Unique paths |
| 2D String | dp[i][j] = f(s1[i], s2[j]) | LCS, Edit distance |
| Knapsack | dp[i][w] = max(take, don't take) | 0-1 Knapsack |
The problem statement usually names the pattern. One sequence and a choice at each position points to 1D. Two strings or a grid points to 2D indexed by position in each. A capacity, budget or target sum with items to pick points to knapsack, and “each item at most once” versus “unlimited” decides whether the 1D loop runs downward or upward. “Subsequence” allows skipping elements and “subarray” or “substring” does not, which changes whether dp[i] means “best ending exactly at i” or “best among the first i”.
When none of these fits, the state probably needs another dimension, for example the last element chosen or whether you are currently holding a stock.
Recommended Problems
Baekjoon
LeetCode
- LeetCode 70: Climbing Stairs
- LeetCode 198: House Robber
- LeetCode 62: Unique Paths
- LeetCode 1143: Longest Common Subsequence
- LeetCode 72: Edit Distance
- LeetCode 300: Longest Increasing Subsequence
Programmers
Related Articles
- Dynamic Programming (DP) | Essential Algorithm for Coding Interviews
- Algorithm Series Full Index
- Arrays and Lists
- Stack and Queue
- DP Practice Problems
- Greedy Algorithms