Dynamic programming is the hardest interview topic, but most DP problems follow a few common patterns. If you learn these patterns, you can solve new DP problems by recognizing which pattern applies. In this article, you will learn six DP patterns with full examples.
We show core examples in Kotlin, Python, and Go.
The 4-Step Approach to Any DP Problem
- Start with brute force recursion. Write the recursive solution without worrying about efficiency.
- Add memoization. Cache results of subproblems.
- Convert to bottom-up. Fill a table iteratively.
- Optimize space. Reduce memory if possible.
Pattern 1: Linear DP
Each state depends on one or two previous states. This is the simplest DP pattern.
Maximum Subarray (Kadane’s Algorithm)
Find the contiguous subarray with the largest sum.
Python:
def max_subarray(nums):
current_sum = max_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
Kotlin:
fun maxSubArray(nums: IntArray): Int {
var currentSum = nums[0]
var maxSum = nums[0]
for (i in 1 until nums.size) {
currentSum = maxOf(nums[i], currentSum + nums[i])
maxSum = maxOf(maxSum, currentSum)
}
return maxSum
}
State: dp[i] = maximum subarray sum ending at index i. Recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i]). Time: O(n). Space: O(1).
Decode Ways
A message encoded as digits can be decoded into letters (1=A, 2=B, …, 26=Z). Count the number of ways to decode it.
Python:
def num_decodings(s):
if not s or s[0] == "0":
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
if s[i - 1] != "0":
dp[i] += dp[i - 1]
two_digit = int(s[i - 2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i - 2]
return dp[n]
Pattern 2: Knapsack
Choose items to maximize value without exceeding a capacity. Two variants:
- 0/1 Knapsack: Each item can be used once
- Unbounded Knapsack: Each item can be used unlimited times
0/1 Knapsack Template
Python:
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] # Skip item i
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]
Partition Equal Subset Sum
Can you partition an array into two subsets with equal sum? This is a 0/1 knapsack where target = total_sum / 2.
Python:
def can_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target]
Go:
func canPartition(nums []int) bool {
total := 0
for _, n := range nums {
total += n
}
if total%2 != 0 {
return false
}
target := total / 2
dp := make([]bool, target+1)
dp[0] = true
for _, num := range nums {
for j := target; j >= num; j-- {
dp[j] = dp[j] || dp[j-num]
}
}
return dp[target]
}
Time: O(n * target). Space: O(target).
Coin Change (Unbounded Knapsack)
Each coin can be used unlimited times. This is the unbounded variant.
Python:
def coin_change(coins, amount):
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
return dp[amount] if dp[amount] != float("inf") else -1
Notice the inner loop iterates forward (not backward like 0/1 knapsack), because we can reuse coins.
Pattern 3: String DP
Compare two strings character by character. Usually a 2D table where dp[i][j] represents the answer for the first i characters of string 1 and first j characters of string 2.
Edit Distance
Find the minimum number of operations (insert, delete, replace) to convert one string to another.
Python:
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
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]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # Delete
dp[i][j - 1], # Insert
dp[i - 1][j - 1], # Replace
)
return dp[m][n]
Kotlin:
fun minDistance(word1: String, word2: String): Int {
val m = word1.length
val n = word2.length
val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 0..m) dp[i][0] = i
for (j in 0..n) dp[0][j] = j
for (i in 1..m) {
for (j in 1..n) {
dp[i][j] = if (word1[i - 1] == word2[j - 1]) {
dp[i - 1][j - 1]
} else {
1 + minOf(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
}
}
}
return dp[m][n]
}
Time: O(m * n). Space: O(m * n).
Palindromic Substrings
Count the number of palindromic substrings.
Python:
def count_substrings(s):
n = len(s)
count = 0
def expand(left, right):
nonlocal count
while left >= 0 and right < n and s[left] == s[right]:
count += 1
left -= 1
right += 1
for i in range(n):
expand(i, i) # Odd length
expand(i, i + 1) # Even length
return count
Time: O(n^2). Alternatively, use a DP table where dp[i][j] = True if s[i:j+1] is a palindrome.
Pattern 4: Grid DP
Navigate a grid, computing optimal values. Each cell depends on its neighbors (usually top and left).
Minimum Path Sum
Find the path from top-left to bottom-right with the minimum sum. You can only move right or down.
Python:
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
for i in range(1, m):
grid[i][0] += grid[i - 1][0]
for j in range(1, n):
grid[0][j] += grid[0][j - 1]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
return grid[m - 1][n - 1]
Go:
func minPathSum(grid [][]int) int {
m, n := len(grid), len(grid[0])
for i := 1; i < m; i++ {
grid[i][0] += grid[i-1][0]
}
for j := 1; j < n; j++ {
grid[0][j] += grid[0][j-1]
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
}
}
return grid[m-1][n-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Time: O(m * n). Space: O(1) if we modify the grid in-place.
Pattern 5: Interval DP
Compute the best result for a range [i, j]. Try all possible split points k between i and j.
Burst Balloons
Burst balloons to maximize coins. When you burst balloon i, you get nums[i-1] * nums[i] * nums[i+1] coins.
Python:
def max_coins(nums):
nums = [1] + nums + [1]
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):
dp[left][right] = max(
dp[left][right],
dp[left][k] + dp[k][right] + nums[left] * nums[k] * nums[right],
)
return dp[0][n - 1]
Time: O(n^3). Space: O(n^2).
Pattern 6: State Machine DP
Track multiple states (like “holding a stock” vs “not holding”). Transition between states based on actions.
Best Time to Buy and Sell Stock with Cooldown
Buy and sell stock with a 1-day cooldown after selling.
Python:
def max_profit(prices):
if len(prices) < 2:
return 0
n = len(prices)
# Three states: hold, sold (cooldown), rest (can buy)
hold = -prices[0]
sold = 0
rest = 0
for i in range(1, n):
prev_hold = hold
prev_sold = sold
prev_rest = rest
hold = max(prev_hold, prev_rest - prices[i])
sold = prev_hold + prices[i]
rest = max(prev_rest, prev_sold)
return max(sold, rest)
Kotlin:
fun maxProfit(prices: IntArray): Int {
if (prices.size < 2) return 0
var hold = -prices[0]
var sold = 0
var rest = 0
for (i in 1 until prices.size) {
val prevHold = hold
val prevSold = sold
val prevRest = rest
hold = maxOf(prevHold, prevRest - prices[i])
sold = prevHold + prices[i]
rest = maxOf(prevRest, prevSold)
}
return maxOf(sold, rest)
}
Time: O(n). Space: O(1).
Pattern Recognition Guide
| If the problem involves… | DP Pattern |
|---|---|
| Single array, previous elements | Linear DP |
| Choose/skip items with capacity | Knapsack |
| Two strings, comparing characters | String DP |
| Grid with movements | Grid DP |
| Range [i, j] with split points | Interval DP |
| Multiple states per position | State Machine DP |
Common Mistakes
Not starting with brute force. You cannot optimize what you do not understand. Always write the recursive solution first.
Wrong iteration direction in space optimization. For 0/1 knapsack, iterate capacity backward. For unbounded, iterate forward.
Missing base cases. Every DP needs explicit base cases. Check dp[0], dp[1], or dp[0][0] carefully.
Using the wrong pattern. Partition Equal Subset Sum looks like it could be backtracking, but it is a knapsack problem. Take time to identify the pattern.
Practice Problems
| Problem | Pattern | LeetCode # |
|---|---|---|
| Maximum Subarray | Linear | #53 |
| Coin Change | Unbounded Knapsack | #322 |
| Partition Equal Subset Sum | 0/1 Knapsack | #416 |
| Edit Distance | String DP | #72 |
| Minimum Path Sum | Grid DP | #64 |
| Burst Balloons | Interval DP | #312 |
| Best Time to Buy/Sell Stock (Cooldown) | State Machine | #309 |
| Word Break | Linear | #139 |
What’s Next?
You now know the core DP patterns. The next article compares System Design vs DSA — when you need which in interviews and how to allocate your study time.
Next: DSA Tutorial #23: System Design vs DSA
Full series: DSA from Zero to Interview Ready