8 drills · 8 pattern exercises · 15 micro drills
Patterns used in this topic, with difficulty breakdown.
Count the number of different ways to reach the top of a staircase if you can take 1 or 2 steps at a time.
All 8 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Count the number of different ways to reach the top of a staircase if you can take 1 or 2 steps at a time.
To reach step n you came from step n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2) — the same recurrence as Fibonacci.
Prompt
You can climb 1 or 2 steps at a time. How many distinct ways can you climb n stairs?
Solution
def climb_stairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b # ways[i] = ways[i-1] + ways[i-2]
return b
# Test: climb_stairs(2) == 2
# Test: climb_stairs(3) == 3
# Test: climb_stairs(5) == 8In plain English: Find the fewest coins needed to make a given amount of money, or say it is impossible.
Build a table where dp[i] = min coins for amount i. For each amount, try every coin and take the best — classic unbounded knapsack.
Prompt
Given coin denominations and a target amount, find the minimum number of coins needed. Return -1 if impossible.
Solution
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i and dp[i - c] + 1 < dp[i]:
dp[i] = dp[i - c] + 1 # use coin c
return dp[amount] if dp[amount] != float('inf') else -1
# Test: coin_change([1,5,10,25], 30) == 2 (25+5)
# Test: coin_change([2], 3) == -1In plain English: Find the longest chain of numbers in an array that are strictly increasing (not necessarily adjacent).
For each element, check all previous elements — if a[j] < a[i], then dp[i] = max(dp[i], dp[j]+1). The O(n log n) approach uses patience sorting.
Prompt
Given an array of integers, find the length of the longest strictly increasing subsequence.
Solution
import bisect
def length_of_lis(nums):
# O(n log n) using patience sorting
tails = []
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x) # extend longest subsequence
else:
tails[pos] = x # replace to keep smallest tail
return len(tails)
# Test: length_of_lis([10,9,2,5,3,7,101,18]) == 4 (2,3,7,101)
# Test: length_of_lis([0,1,0,3,2,3]) == 4In plain English: Find the cheapest path from the top-left to the bottom-right of a grid, moving only right or down.
Each cell's minimum cost is its own value plus the cheaper of the cell above or to the left — fill row by row in O(mn).
Prompt
Given an m x n grid of non-negative integers, find a path from top-left to bottom-right that minimizes the sum. You can only move right or down.
Solution
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = grid[0][0]
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j]
for i in range(1, m):
dp[0] += grid[i][0]
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j - 1]) # min of above, left
return dp[-1]
# Test: min_path_sum([[1,3,1],[1,5,1],[4,2,1]]) == 7 (1->3->1->1->1)In plain English: Find the fewest edits (insert, delete, or replace a character) to turn one word into another.
Build a 2D table where dp[i][j] = edit distance between word1[:i] and word2[:j]. If chars match, no cost; otherwise take min of insert, delete, replace plus 1.
Prompt
Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) to convert word1 into word2.
Solution
def edit_distance(w1, w2):
m, n = len(w1), len(w2)
dp = list(range(n + 1)) # base: transforming "" to w2[:j]
for i in range(1, m + 1):
prev, dp[0] = dp[0], i
for j in range(1, n + 1):
temp = dp[j]
if w1[i - 1] == w2[j - 1]:
dp[j] = prev # match: no extra cost
else:
dp[j] = 1 + min(prev, dp[j], dp[j - 1]) # replace, delete, insert
prev = temp
return dp[n]
# Test: edit_distance("horse", "ros") == 3
# Test: edit_distance("intention", "execution") == 5In plain English: Count how many valid letter-decodings a string of digits can have, where 1-26 each map to A-Z.
At each position, you can decode one digit (1-9) or two digits (10-26). dp[i] = dp[i-1] (one digit) + dp[i-2] (two digits) when valid.
Prompt
Given a string of digits, count the number of ways to decode it into letters (A=1, B=2, ..., Z=26).
Solution
def num_decodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
prev2, prev1 = 1, 1 # dp[0], dp[1]
for i in range(1, n):
cur = 0
if s[i] != '0':
cur += prev1 # single digit decode
two = int(s[i - 1:i + 1])
if 10 <= two <= 26:
cur += prev2 # two digit decode
prev2, prev1 = prev1, cur
return prev1
# Test: num_decodings("12") == 2 ("AB" or "L")
# Test: num_decodings("226") == 3 ("BZ", "VF", "BBF")
# Test: num_decodings("06") == 0In plain English: Pick non-adjacent houses to rob so the total money is maximized.
At each house, choose the better of: rob it (skip previous) or skip it (keep previous best). Two variables track these rolling choices.
Prompt
Given an array of house values, find the maximum amount you can rob without robbing two adjacent houses.
Solution
def rob(nums):
if not nums:
return 0
prev2, prev1 = 0, 0
for x in nums:
# include current + skip previous, or exclude current
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
# Test: rob([1,2,3,1]) == 4 (rob house 0 and 2)
# Test: rob([2,7,9,3,1]) == 12 (rob house 0, 2, 4)In plain English: Pack a bag with items of different weights and values to maximize total value without going over the weight limit.
For each item, decide include or exclude. dp[w] = max value achievable with capacity w. Process items in reverse to avoid reuse.
Prompt
Given n items with weights and values and a capacity W, find the maximum value you can carry without exceeding W. Each item can be used at most once.
Solution
def knapsack(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
# reverse to ensure each item used at most once
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
# Test: knapsack([1,3,4,5], [1,4,5,7], 7) == 9 (items 1,2: weight 3+4=7, value 4+5=9)
# Test: knapsack([2,3,4,5], [3,4,5,6], 5) == 78 exercises: spot the signals, pick the method, avoid the trap.
You can climb 1 or 2 steps. How many distinct ways to climb n stairs?
Signals
dp[i] = dp[i-1] + dp[i-2]. Start: dp[0]=1, dp[1]=1. O(n) time, O(1) space with two variables.
Recursive with memoization. Same O(n) but uses O(n) stack space.
Trap
Recognize this IS Fibonacci. Don't overthink it.
Max amount you can rob without robbing two adjacent houses.
Signals
dp[i] = max(dp[i-1], dp[i-2] + val[i]). Include or exclude each house. O(n) time, O(1) space.
Trap
Greedy (always rob the largest) fails — adjacent constraint makes local greedy suboptimal.
Given coin denominations and a target, find minimum coins needed.
Signals
dp[i] = min coins for amount i. For each amount, try every coin. O(amount * coins).
Greedy (largest coin first) FAILS for non-standard denominations (e.g., coins [1,3,4], target 6).
Trap
Greedy seems intuitive but doesn't always give optimal. DP is needed for correctness.
Find the length of the longest strictly increasing subsequence.
Signals
dp[i] = length of LIS ending at i. For each j < i where a[j] < a[i]: dp[i] = max(dp[j]+1). O(n²).
Maintain a 'tails' array + bisect_left for O(n log n). More efficient but harder to implement.
Trap
Subsequence ≠ subarray. Elements can be non-contiguous. This changes the approach fundamentally.
Maximize value in a knapsack of capacity W, each item used at most once.
Signals
dp[i][w] = max value with first i items and capacity w. Include or exclude each item. O(n*W).
Trap
Greedy (best value/weight ratio) doesn't work for 0/1 knapsack. DP is required.
Find path from top-left to bottom-right minimizing sum. Move only right or down.
Signals
Fill grid: each cell = own value + min(above, left). O(m*n) time. Can reuse the grid for O(1) extra space.
Trap
BFS/DFS would explore too many paths. The constraint (only right/down) makes DP perfect — no cycles.
Minimum operations (insert, delete, replace) to convert word1 into word2.
Signals
2D DP. If chars match, dp[i][j] = dp[i-1][j-1]. Else min(insert, delete, replace) + 1. O(m*n).
Trap
No greedy shortcut exists. The 2D DP is the canonical approach — know it cold.
Count ways to decode a digit string into letters (A=1, B=2, ..., Z=26).
Signals
dp[i] = dp[i-1] if valid single digit + dp[i-2] if valid two digits. O(n) time.
Trap
'0' is not a valid single digit — handle it. '06' is not a valid two-digit code. Edge cases matter.
15 quick recall drills to reinforce this topic.
dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Optimized to two variables. Final answer is min of last two.
def minCostClimbingStairs(cost):
a, b = cost[0], cost[1]
for i in range(2, len(cost)):
a, b = b, cost[i] + min(a, b)
return min(a, b)At each house: rob it (prev2 + current) or skip it (prev1). Classic two-variable DP.
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = 0, 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1Circular constraint: first and last are adjacent. Solve twice: once excluding first, once excluding last.
def rob(nums):
if len(nums) == 1: return nums[0]
def rob_linear(arr):
prev2, prev1 = 0, 0
for x in arr:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
return max(rob_linear(nums[1:]), # skip first
rob_linear(nums[:-1])) # skip lastAt each element: extend current subarray or start fresh. The simplest DP pattern — must be instant.
def maxSubArray(nums):
cur = res = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
res = max(res, cur)
return resCounting coin combinations iterates coins outer to avoid permutation double-counting.
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for a in range(c, amount + 1):
dp[a] += dp[a - c]Unbounded knapsack DP: iterate coins outer, amounts inner. Classic DP problem.
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)Single-pass tracking of running minimum and maximum profit. Classic greedy O(n) solution.
mn = float('inf')
mx = 0
for p in prices:
mn = min(mn, p)
mx = max(mx, p - mn)dp[i] = length of longest increasing subsequence ending at index i. Classic O(n²) DP.
def lengthOfLIS(nums):
n = len(nums)
dp = [1] * n # each element is a subsequence of length 1
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)2D interval DP. Iterate i from bottom-up so dp[i+1] is already computed. Equivalent to LCS(s, reverse(s)).
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
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]Patience sorting: maintain smallest possible tails. bisect_left finds where to place each element.
import bisect
def lengthOfLIS(nums):
tails = [] # tails[i] = smallest tail of IS of length i+1
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)The inner loop goes BACKWARDS to prevent reusing item i. Forward loop = unbounded knapsack.
def knapsack(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1): # backwards!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]Move-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return wClassic 2D grid DP. Each cell = its value + min(top, left). In-place to avoid extra space.
def minPathSum(grid):
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
elif i == 0: grid[i][j] += grid[i][j-1]
elif j == 0: grid[i][j] += grid[i-1][j]
else: grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]Like climbing stairs but with validity checks. Single digit (1-9) adds dp[i-1], two digits (10-26) adds dp[i-2].
def numDecodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
if s[i-1] != '0':
dp[i] += dp[i-1]
two = int(s[i-2:i])
if 10 <= two <= 26:
dp[i] += dp[i-2]
return dp[n]