Introduction
Dynamic Programming (DP) is an optimization technique for solving problems with overlapping subproblems. When you solve problems recursively, you may encounter the same subproblem multiple times, computing its value redundantly.
Example: Fibonacci Numbers. F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1. Computing F(4) = F(3) + F(2) = (F(2) + F(1)) + F(2) shows F(2) is computed twice.
We can "remember" computed values in a dictionary (memoization). If the value exists, look it up rather than recomputing. This distinguishes DP from regular recursion.
Another perspective: DP is a smart brute force. At each step, we try all possibilities (ensuring correctness), but we avoid exponential time by storing pre-computed cases.
Types of DP we'll cover: Take/don't take, bitmask DP, digit DP, DP on graphs/trees/tries, sliding window DP, DP with binary search, and more.
The key to DP is recursion. Assume you have a function dp that solves your problem. Think about how to use this "magic function" on subproblems and combine results for the current input.
Example: Define sum(i) = sum of A[i:]. If sum(i) works for i > 0, then sum(0) = A[0] + sum(1). This is the recurrence relation.
O(number of states × time per state)O(number of states)Memoized Template (Top-Down)
Use a dictionary or @cache decorator to store computed values.
# Method 1: Manual memoization
def f(self, n: int) -> int:
memo = {}
def dp(n):
if n in [0, 1]: return n # BASE CASE(s)
if n in memo: return memo[n] # Look up
memo[n] = dp(n-1) + dp(n-2) # Store result
return memo[n]
return dp(n)
# Method 2: Using @cache decorator (preferred)
def f(self, n: int) -> int:
@cache
def dp(n):
if n in [0, 1]: return n # BASE CASE(s)
return dp(n-1) + dp(n-2) # Recurse on subproblems
return dp(n)Bottom-Up Template (Optional)
Compute iteratively from base cases up to n. Can optimize space but is more error-prone. Focus on top-down for interviews.
def f(self, n: int) -> int:
if n == 0: return 0
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1 # Base cases
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2] # Recurrence relation
return dp[n]
# Space-optimized O(1) version
def f(self, n: int) -> int:
if n in [0, 1]: return n
dp_0, dp_1 = 0, 1
for _ in range(n - 1):
dp_0, dp_1 = dp_1, dp_0 + dp_1
return dp_1Intro DP Problems
Fundamental DP problems to build intuition. These cover the basic patterns: simple recursion, take-or-don't-take, and multi-state DP.
01Fibonacci NumberEasy
The Fibonacci numbers F(n) are defined as: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n > 1. Given n, calculate F(n).
def fib(self, n: int) -> int:
@cache
def dp(n):
if n in [0, 1]: return n
return dp(n-1) + dp(n-2)
return dp(n)O(n)O(n)This is the definition of DP! Once you have the recurrence relation and base cases, the code writes itself. The hard part is discovering the correct recurrence.
02Climbing StairsEasy
You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?
def climbStairs(self, n: int) -> int:
@cache
def dp(i):
if i <= 1: return 1
return dp(i-1) + dp(i-2)
return dp(n)O(n)O(n)dp(i) = number of ways to climb i steps. We reach step i from step i-1 (1 step) or step i-2 (2 steps). Base case: dp(0) = dp(1) = 1.
03Min Cost Climbing StairsEasy
Given an array cost where cost[i] is the cost of step i, find minimum cost to reach the top. You can start from step 0 or 1.
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
@cache
def dp(i):
if i >= n: return 0
return cost[i] + min(dp(i+1), dp(i+2))
return min(dp(0), dp(1))O(n)O(n)dp(i) = min cost to reach top starting from step i. We must pay cost[i], then choose cheaper of next 1 or 2 steps.
04House RobberMedium
Given an array of house values, rob houses to maximize profit. Cannot rob two adjacent houses.
def rob(self, nums: List[int]) -> int:
@cache
def dp(i):
if i < 0: return 0
return max(nums[i] + dp(i-2), dp(i-1))
return dp(len(nums) - 1)O(n)O(n)Take or don't take pattern. dp(i) = max profit from houses [0..i]. Either rob house i (get nums[i], skip i-1, recurse on i-2) or don't rob (recurse on i-1).
05House Robber IIMedium
Same as House Robber, but houses are arranged in a circle (first and last are adjacent).
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1: return nums[0]
@cache
def dp(i, min_idx):
if i < min_idx: return 0
return max(nums[i] + dp(i-2, min_idx), dp(i-1, min_idx))
# Case 1: Rob house 0 → can't rob house 1 or n-1
# Case 2: Don't rob house 0 → can rob houses 1 to n-1
return max(nums[0] + dp(n-2, 2), dp(n-1, 1))O(n)O(n)Split into two cases: either rob house 0 (then solve linear problem on [2, n-2]) or don't rob house 0 (solve on [1, n-1]).
06Domino and Tromino TilingMedium
Count ways to tile a 2×n board with dominoes (2×1) and trominoes (L-shaped).
def numTilings(self, n: int) -> int:
MOD = 10**9 + 7
@cache
def dp(i):
if i <= 1: return 1
if i == 2: return 2
return (dp(i-1) + dp(i-2) + 2 * dp(i-3) +
2 * sum(dp(j) for j in range(i-3))) % MOD
return dp(n)
# Optimized with prefix sum
def numTilings(self, n: int) -> int:
MOD = 10**9 + 7
@cache
def prefix(i):
if i < 0: return 0
return (prefix(i-1) + dp(i)) % MOD
@cache
def dp(i):
if i < 0: return 0
if i <= 1: return 1
return (dp(i-1) + dp(i-2) + 2 * prefix(i-3)) % MOD
return dp(n)O(n)O(n)This requires tracking a "partial" state where one square sticks out. The recurrence is more complex - need dp(i) for complete rows and track prefix sums for tromino combinations.
Classical DP Problems
Classic DP problems that appear frequently in interviews. These cover coin change, partition problems, and grid-based DP.
01Coin ChangeMedium
Given coins of different denominations and a total amount, find the fewest coins needed to make that amount. Return -1 if impossible.
def coinChange(self, coins: List[int], amount: int) -> int:
@cache
def dp(amt):
if amt == 0: return 0
if amt < 0: return inf
return 1 + min((dp(amt - c) for c in coins), default=inf)
res = dp(amount)
return res if res != inf else -1O(amount × len(coins))O(amount)Try all possibilities pattern. For each amount, try using each coin and take the minimum. Base case: 0 coins needed for amount 0.
02Partition Equal Subset SumMedium
Given an integer array nums, return true if you can partition it into two subsets with equal sum.
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0: return False
target = total // 2
@cache
def dp(i, remaining):
if remaining == 0: return True
if i >= len(nums) or remaining < 0: return False
return dp(i+1, remaining - nums[i]) or dp(i+1, remaining)
return dp(0, target)O(n × sum)O(n × sum)If total is odd, impossible. Otherwise, find if any subset sums to total/2. Use take-or-don't-take pattern for each element.
03Maximal SquareMedium
Given an m×n binary matrix, find the largest square containing only 1's and return its area.
def maximalSquare(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
@cache
def dp(i, j):
if i >= m or j >= n or matrix[i][j] == '0':
return 0
return 1 + min(dp(i+1, j), dp(i, j+1), dp(i+1, j+1))
res = max(dp(i, j) for i in range(m) for j in range(n))
return res * resO(m × n)O(m × n)dp(i,j) = side length of largest square with top-left corner at (i,j). A square exists only if current cell is 1 AND squares exist to the right, below, and diagonally.
04Count Square Submatrices with All OnesMedium
Given a binary matrix, count all square submatrices containing only 1's.
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
@cache
def dp(i, j):
if i >= m or j >= n or matrix[i][j] == 0:
return 0
return 1 + min(dp(i + 1, j), dp(i, j + 1), dp(i + 1, j + 1))
return sum(dp(i, j) for i in range(m) for j in range(n))O(m × n)O(m × n)This reuses the Maximal Square recurrence. Instead of only taking the maximum side length, sum dp(i,j) because each top-left cell contributes one square of every size up to that side length.
05Minimum Path SumMedium
Given an m×n grid filled with non-negative numbers, find a path from top-left to bottom-right minimizing the sum. Can only move right or down.
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
@cache
def dp(i, j):
if i == m-1 and j == n-1: return grid[i][j]
if i >= m or j >= n: return inf
return grid[i][j] + min(dp(i+1, j), dp(i, j+1))
return dp(0, 0)O(m × n)O(m × n)Classic grid DP. From each cell, we can go right or down. Take the cheaper path and add current cell's value.
Longest Increasing Subsequence (LIS)
LIS is a fundamental DP pattern. Many problems reduce to LIS. Know both the O(n²) DP solution and the O(n log n) binary search solution.
dp(i) = length of LIS ending at index i. For each j < i where nums[j] < nums[i], we can extend the LIS ending at j.
LIS Templates
Two approaches: O(n²) DP checks all previous indices, O(n log n) uses patience sort with binary search.
# O(n²) DP solution
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
@cache
def dp(i):
res = 1
for j in range(i):
if nums[j] < nums[i]:
res = max(res, 1 + dp(j))
return res
return max(dp(i) for i in range(n))
# O(n log n) patience sort / binary search
def lengthOfLIS(self, nums: List[int]) -> int:
tails = [] # tails[i] = smallest tail of all LIS with length i+1
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)01Longest Increasing SubsequenceMedium
Given an integer array nums, return the length of the longest strictly increasing subsequence.
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)O(n log n)O(n)Maintain array where tails[i] = smallest ending value of all increasing subsequences of length i+1. Binary search to find position for new element.
02Russian Doll EnvelopesHard
Given envelopes as [width, height], find max envelopes you can nest (both dimensions must be strictly greater).
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
# Sort by width ascending, height descending (for same width)
envelopes.sort(key=lambda x: (x[0], -x[1]))
# LIS on heights only
heights = [h for w, h in envelopes]
tails = []
for h in heights:
pos = bisect_left(tails, h)
if pos == len(tails):
tails.append(h)
else:
tails[pos] = h
return len(tails)O(n log n)O(n)Sort by width ascending. For same width, sort height descending (so we can't nest same-width envelopes). Then run LIS on heights.
Longest Common Subsequence (LCS)
LCS finds the longest subsequence common to two sequences. This is another must-know DP pattern.
dp(i, j) = LCS of s[0:i+1] and t[0:j+1]. If s[i] == t[j], we can extend by 1. Otherwise, try skipping from either string.
01Longest Common SubsequenceMedium
Given two strings text1 and text2, return the length of their longest common subsequence.
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
@cache
def dp(i, j):
if i < 0 or j < 0: return 0
if text1[i] == text2[j]:
return 1 + dp(i-1, j-1)
return max(dp(i-1, j), dp(i, j-1))
return dp(len(text1)-1, len(text2)-1)O(m × n)O(m × n)If characters match, extend LCS by 1. Otherwise, try excluding character from either string and take the max.
02Shortest Common SupersequenceHard
Given two strings str1 and str2, return the shortest string that has both as subsequences.
def shortestCommonSupersequence(self, s: str, t: str) -> str:
m, n = len(s), len(t)
@cache
def dp(i, j):
if i < 0 or j < 0: return 0
if s[i] == t[j]:
return 1 + dp(i-1, j-1)
return max(dp(i-1, j), dp(i, j-1))
# Backtrack to construct the answer
i, j = m-1, n-1
res = []
while i >= 0 and j >= 0:
if s[i] == t[j]:
res.append(s[i])
i -= 1
j -= 1
elif dp(i-1, j) >= dp(i, j-1):
res.append(s[i])
i -= 1
else:
res.append(t[j])
j -= 1
# Add remaining characters
while i >= 0:
res.append(s[i])
i -= 1
while j >= 0:
res.append(t[j])
j -= 1
return ''.join(res[::-1])O(m × n)O(m × n)First find LCS, then backtrack to build the supersequence. Include characters not in LCS from both strings, and shared characters once.
03Longest Palindromic SubsequenceMedium
Given a string s, find the longest palindromic subsequence's length.
def longestPalindromeSubseq(self, s: str) -> int:
# LPS(s) = LCS(s, reverse(s))
t = s[::-1]
@cache
def dp(i, j):
if i < 0 or j < 0: return 0
if s[i] == t[j]:
return 1 + dp(i-1, j-1)
return max(dp(i-1, j), dp(i, j-1))
return dp(len(s)-1, len(s)-1)O(n²)O(n²)Key insight: Longest Palindromic Subsequence = LCS of string with its reverse.
04Longest Palindromic Subsequence IIMedium
Find longest good palindromic subsequence: even length, no two consecutive characters equal except middle two.
def longestPalindromeSubseq(self, s: str) -> int:
@cache
def dp(i, j, prev):
if i >= j: return 0
if s[i] == s[j] and s[i] != prev:
return 2 + dp(i + 1, j - 1, s[i])
return max(dp(i + 1, j, prev), dp(i, j - 1, prev))
return dp(0, len(s) - 1, '')O(n² × 26)O(n² × 26)Track previous matched character. Return 0 when i == j to ensure even length only (exclude single middle char).
05Valid Palindrome IIIHard
Return true if string can become palindrome by removing at most k characters.
def isValidPalindrome(self, s: str, k: int) -> bool:
@cache
def dp(i, j):
if i >= j: return i == j
if s[i] == s[j]:
return 2 + dp(i + 1, j - 1)
return max(dp(i + 1, j), dp(i, j - 1))
return dp(0, len(s) - 1) >= len(s) - kO(n²)O(n²)Think in reverse: if we can remove k chars, remaining chars form a palindromic subsequence. Check if LPS length >= n-k.
Best Time to Buy and Sell Stock
A family of problems about maximizing profit from stock transactions with various constraints (cooldown, fees, limited transactions).
01Best Time to Buy and Sell StockEasy
One transaction allowed. Find maximum profit.
def maxProfit(self, prices: List[int]) -> int:
min_price, max_profit = inf, 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profitO(n)O(1)Track minimum price seen so far. At each day, the best profit is selling at current price minus the minimum buy price.
02Best Time to Buy and Sell Stock IIMedium
Unlimited transactions. Find maximum profit.
def maxProfit(self, prices: List[int]) -> int:
return sum(max(0, prices[i] - prices[i-1])
for i in range(1, len(prices)))O(n)O(1)Greedy: capture every upward movement. Equivalent to buying every valley and selling every peak.
03Best Time to Buy and Sell Stock with CooldownMedium
Unlimited transactions, but after selling you must wait one day before buying again.
def maxProfit(self, prices: List[int]) -> int:
@cache
def dp(i, holding):
if i >= len(prices): return 0
if holding:
# Can sell or hold
return max(prices[i] + dp(i+2, False), dp(i+1, True))
else:
# Can buy or skip
return max(-prices[i] + dp(i+1, True), dp(i+1, False))
return dp(0, False)O(n)O(n)State machine DP with states: holding stock or not. After selling (i+2 because cooldown), after buying/holding (i+1).
04Best Time to Buy and Sell Stock with Transaction FeeMedium
Unlimited transactions with a fee per transaction.
def maxProfit(self, prices: List[int], fee: int) -> int:
@cache
def dp(i, holding):
if i >= len(prices): return 0
if holding:
return max(prices[i] - fee + dp(i+1, False), dp(i+1, True))
else:
return max(-prices[i] + dp(i+1, True), dp(i+1, False))
return dp(0, False)O(n)O(n)Same state machine as cooldown, but subtract fee when selling instead of skipping a day.
05Best Time to Buy and Sell Stock IVHard
At most k transactions. Find maximum profit.
def maxProfit(self, k: int, prices: List[int]) -> int:
@cache
def dp(i, k, holding):
if i >= len(prices) or k == 0: return 0
if holding:
return max(prices[i] + dp(i+1, k-1, False), dp(i+1, k, True))
else:
return max(-prices[i] + dp(i+1, k, True), dp(i+1, k, False))
return dp(0, k, False)O(n × k)O(n × k)Add transaction count to state. Decrement k when completing a sell (a full transaction).
Bitmask DP
Use bitmasks to represent subsets in DP state. Useful when n is small (typically n < 20) and we need to track which elements have been used.
A bitmask of n bits can represent any subset of n elements. Bit i being 1 means element i is included. There are 2^n possible subsets, so time complexity is O(n × 2^n).
Bitmask DP Template
Common pattern: dp(mask) where mask tracks which elements have been used/visited.
# Template for bitmask DP
def solve(self, nums: List[int]) -> int:
n = len(nums)
ALL = (1 << n) - 1 # All bits set = all elements used
@cache
def dp(mask, last):
if mask == ALL: return 0 # Base: all elements used
res = inf
for i in range(n):
if mask & (1 << i): continue # Skip if already used
if valid(last, nums[i]): # Check some condition
res = min(res, cost(last, nums[i]) + dp(mask | (1 << i), i))
return res
return dp(0, -1) # Start with empty mask
# Bit operations cheat sheet:
# mask | (1 << i) - Set bit i (add element i)
# mask & (1 << i) - Check if bit i is set
# mask & ~(1 << i) - Clear bit i (remove element i)
# mask ^ (1 << i) - Toggle bit i01Special PermutationsMedium
Count permutations where adjacent elements satisfy: nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.
def specialPerm(self, nums: List[int]) -> int:
n = len(nums)
MOD = 10**9 + 7
ALL = (1 << n) - 1
@cache
def dp(mask, prev):
if mask == ALL: return 1
res = 0
for i in range(n):
if mask & (1 << i): continue
if nums[i] % prev == 0 or prev % nums[i] == 0:
res = (res + dp(mask | (1 << i), nums[i])) % MOD
return res
return dp(0, 1) # prev=1 so any nums[i] % 1 == 0O(n² × 2^n)O(n × 2^n)Track which elements used (bitmask) and previous element. Try adding each unused element that satisfies the divisibility condition.
02Smallest Sufficient TeamHard
Given required skills and people with skills, find smallest team covering all skills.
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
skill_idx = {s: i for i, s in enumerate(req_skills)}
n = len(req_skills)
ALL = (1 << n) - 1
# Convert each person's skills to bitmask
person_masks = []
for person in people:
mask = 0
for skill in person:
if skill in skill_idx:
mask |= (1 << skill_idx[skill])
person_masks.append(mask)
@cache
def dp(mask):
if mask == ALL: return []
res = None
for i, pmask in enumerate(person_masks):
if pmask & ~mask: # Person has skills we need
team = dp(mask | pmask)
if res is None or len(team) + 1 < len(res):
res = [i] + team
return res if res else list(range(len(people))) # Fallback
return dp(0)O(people × 2^skills)O(2^skills)Bitmask represents which skills are covered. For each state, try adding each person and take the smallest team.
Digit DP
Count numbers in a range [0, N] satisfying some property. Process digits from left to right, tracking whether we're still bounded by N.
Key states: (position, is_tight, is_leading_zero, extra_properties). is_tight means we're still at the boundary of N. is_leading_zero handles numbers like 007.
Digit DP Template
Standard template for counting numbers with a property up to N.
def count(digits: str) -> int:
@cache
def dp(i, tight, leading_zero, extra_state):
if i == len(digits):
return 1 if valid(extra_state) else 0
max_digit = int(digits[i]) if tight else 9
res = 0
for d in range(max_digit + 1):
next_tight = tight and (d == max_digit)
next_leading = leading_zero and (d == 0)
next_state = update_state(extra_state, d, next_leading)
res += dp(i + 1, next_tight, next_leading, next_state)
return res
return dp(0, True, True, initial_state)
# To count in range [low, high]:
# return count(high) - count(str(int(low) - 1))01Count Stepping Numbers in RangeHard
Count stepping numbers in [low, high] where adjacent digits differ by exactly 1.
def countSteppingNumbers(self, low: str, high: str) -> int:
MOD = 10**9 + 7
def count(digits):
@cache
def dp(i, tight, leading_zero, prev):
if i == len(digits): return 1
max_d = int(digits[i]) if tight else 9
res = 0
for d in range(max_d + 1):
next_tight = tight and d == max_d
next_leading = leading_zero and d == 0
if next_leading:
res = (res + dp(i+1, next_tight, True, -1)) % MOD
elif prev == -1 or abs(d - prev) == 1:
res = (res + dp(i+1, next_tight, False, d)) % MOD
return res
return dp(0, True, True, -1)
return (count(high) - count(str(int(low) - 1))) % MODO(digits × 10)O(digits × 10)Track previous digit to check stepping condition. Leading zeros don't count as real digits, so prev stays -1.
02Count of IntegersHard
Count integers in [num1, num2] where digit sum is in [min_sum, max_sum].
def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
MOD = 10**9 + 7
def count_up_to(s):
@cache
def dp(i, digit_sum, tight):
if i == len(s):
return 1 if min_sum <= digit_sum <= max_sum else 0
max_d = int(s[i]) if tight else 9
res = 0
for d in range(max_d + 1):
next_tight = tight and d == max_d
res = (res + dp(i+1, digit_sum + d, next_tight)) % MOD
return res
return dp(0, 0, True)
return (count_up_to(num2) - count_up_to(str(int(num1) - 1))) % MODO(digits × max_sum)O(digits × max_sum)Track running digit sum. At the end, check if sum is in valid range. No need for leading zero tracking here.
DP with Binary Search / Intervals
Problems involving intervals or scheduling where we need to find the next valid position efficiently using binary search.
01Maximum Profit in Job SchedulingHard
Given jobs with start time, end time, and profit, find maximum profit with non-overlapping jobs.
def jobScheduling(self, startTime: List[int], endTime: List[int],
profit: List[int]) -> int:
jobs = sorted(zip(startTime, endTime, profit))
@cache
def dp(i):
if i >= len(jobs): return 0
# Binary search for next job we can take
start, end, p = jobs[i]
next_idx = bisect_left(jobs, (end,), key=lambda x: x[0])
# Take this job or skip it
return max(p + dp(next_idx), dp(i + 1))
return dp(0)O(n log n)O(n)Sort by start time. For each job, either take it (add profit, skip to next non-overlapping job via binary search) or skip it.
02Maximum Earnings From TaxiMedium
Pick up passengers with [start, end, tip]. Earn end-start+tip per ride. Maximize earnings.
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
rides.sort()
@cache
def dp(i):
if i >= len(rides): return 0
start, end, tip = rides[i]
earn = end - start + tip
next_idx = bisect_left(rides, (end,), key=lambda x: x[0])
return max(earn + dp(next_idx), dp(i + 1))
return dp(0)O(n log n)O(n)Identical structure to job scheduling. Sort rides, use binary search to find next available ride after current ends.
03Minimum Cost For TicketsMedium
Given travel days and ticket costs for 1-day, 7-day, and 30-day passes, find minimum cost to cover all travel days.
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
day_set = set(days)
@cache
def dp(day):
if day > days[-1]: return 0
if day not in day_set: return dp(day + 1)
return min(
costs[0] + dp(day + 1), # 1-day pass
costs[1] + dp(day + 7), # 7-day pass
costs[2] + dp(day + 30) # 30-day pass
)
return dp(days[0])O(max(days))O(max(days))For each travel day, try all three ticket types. Skip non-travel days. Take minimum cost option.
String DP
DP problems on strings including pattern matching, edit distance, and decoding.
01Edit DistanceMedium
Find minimum operations (insert, delete, replace) to convert word1 to word2.
def minDistance(self, word1: str, word2: str) -> int:
@cache
def dp(i, j):
if i < 0: return j + 1 # Insert remaining
if j < 0: return i + 1 # Delete remaining
if word1[i] == word2[j]:
return dp(i-1, j-1) # Match, no cost
return 1 + min(
dp(i-1, j-1), # Replace
dp(i-1, j), # Delete from word1
dp(i, j-1) # Insert into word1
)
return dp(len(word1)-1, len(word2)-1)O(m × n)O(m × n)Classic string DP. If characters match, no operation needed. Otherwise, try all three operations and take minimum.
02Regular Expression MatchingHard
Implement regex matching with '.' (any char) and '*' (zero or more of preceding).
def isMatch(self, s: str, p: str) -> bool:
@cache
def dp(i, j):
if j >= len(p): return i >= len(s)
first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
if j + 1 < len(p) and p[j+1] == '*':
# '*' matches zero OR one+ of preceding
return dp(i, j+2) or (first_match and dp(i+1, j))
else:
return first_match and dp(i+1, j+1)
return dp(0, 0)O(m × n)O(m × n)Handle '*' by either matching zero (skip pattern by 2) or matching one+ (if first matches, advance string but keep pattern).
03Decode WaysMedium
Count ways to decode a digit string where 'A'=1, 'B'=2, ..., 'Z'=26.
def numDecodings(self, s: str) -> int:
@cache
def dp(i):
if i >= len(s): return 1
if s[i] == '0': return 0
# Take one digit
res = dp(i + 1)
# Take two digits if valid (10-26)
if i + 1 < len(s) and 10 <= int(s[i:i+2]) <= 26:
res += dp(i + 2)
return res
return dp(0)O(n)O(n)At each position, try decoding one digit (if not '0') or two digits (if forms valid number 10-26). Sum the ways.
04Wildcard MatchingHard
Match string s with pattern p where '?' matches any single char, '*' matches any sequence.
def isMatch(self, s: str, p: str) -> bool:
@cache
def dp(i, j):
if i == len(s) and j == len(p):
return True
if j == len(p):
return False
if i == len(s):
return p[j] == '*' and dp(i, j + 1)
if p[j] == '?' or s[i] == p[j]:
return dp(i + 1, j + 1)
elif p[j] == '*':
# Match nothing (j+1) or match one char (i+1, keep *)
return dp(i, j + 1) or dp(i + 1, j)
return False
return dp(0, 0)O(m × n)O(m × n)Similar to regex but simpler. '*' can match empty (move j) or consume one char (move i, keep j). '?' must match exactly one char.
05Word BreakMedium
Given string s and dictionary wordDict, return true if s can be segmented into dictionary words.
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
@cache
def dp(i):
if i == len(s):
return True
for j in range(i + 1, len(s) + 1):
if s[i:j] in words and dp(j):
return True
return False
return dp(0)O(n² × m)O(n)Try all prefixes starting at i. If prefix is in dictionary and rest can be segmented, return True.
06Minimum Number of Valid Strings to Form Target IMedium
Form target using minimum number of prefixes from given words array.
def minValidStrings(self, words: List[str], target: str) -> int:
# Build trie of all prefixes
trie = {}
for word in words:
node = trie
for c in word:
if c not in node:
node[c] = {}
node = node[c]
@cache
def dp(i):
if i == len(target):
return 0
node = trie
res = float('inf')
for j in range(i, len(target)):
if target[j] not in node:
break
node = node[target[j]]
res = min(res, 1 + dp(j + 1))
return res
ans = dp(0)
return ans if ans != float('inf') else -1O(n × m)O(total prefix length)Build trie of all word prefixes. DP tries all valid prefixes at each position, taking minimum count.
07Construct String with Minimum CostHard
Form target using words where each word has a cost. Minimize total cost.
def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
# Trie with minimum cost at each node
trie = {}
for word, cost in zip(words, costs):
node = trie
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['$'] = min(node.get('$', float('inf')), cost)
@cache
def dp(i):
if i == len(target):
return 0
node = trie
res = float('inf')
for j in range(i, len(target)):
if target[j] not in node:
break
node = node[target[j]]
if '$' in node:
res = min(res, node['$'] + dp(j + 1))
return res
ans = dp(0)
return ans if ans != float('inf') else -1O(n × m)O(total word length)Similar to word break but with costs. Trie stores minimum cost to form each word. DP finds minimum cost segmentation.
Grid DP
Path counting and optimization problems on 2D grids.
01Unique PathsMedium
Count paths from top-left to bottom-right, moving only right or down.
def uniquePaths(self, m: int, n: int) -> int:
@cache
def dp(i, j):
if i == m - 1 and j == n - 1:
return 1
if i >= m or j >= n:
return 0
return dp(i + 1, j) + dp(i, j + 1)
return dp(0, 0)O(m × n)O(m × n)Classic grid DP. Each cell's count = sum of paths from right and down neighbors.
02Unique Paths IIMedium
Same as Unique Paths but with obstacles (marked as 1).
def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
@cache
def dp(i, j):
if i >= m or j >= n or grid[i][j] == 1:
return 0
if i == m - 1 and j == n - 1:
return 1
return dp(i + 1, j) + dp(i, j + 1)
return dp(0, 0)O(m × n)O(m × n)Add obstacle check - return 0 if cell is blocked.
0301 MatrixMedium
Given a binary matrix, return for each cell the distance to the nearest 0.
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m, n = len(mat), len(mat[0])
INF = m + n + 1
dist = [[0 if mat[i][j] == 0 else INF for j in range(n)] for i in range(m)]
for i in range(m):
for j in range(n):
if i > 0:
dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)
if j > 0:
dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if i + 1 < m:
dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
if j + 1 < n:
dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)
return distO(m × n)O(m × n)Two-pass grid DP: the forward pass sees nearest zeros from top/left, and the backward pass sees nearest zeros from bottom/right. Multi-source BFS is another valid source-backed solution.
04Knight DialerMedium
Count distinct phone numbers of length n a chess knight can dial.
def knightDialer(self, n: int) -> int:
MOD = 10 ** 9 + 7
# Knight moves from each digit
moves = {
0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
4: [0, 3, 9], 5: [], 6: [0, 1, 7], 7: [2, 6],
8: [1, 3], 9: [2, 4]
}
@cache
def dp(digit, remaining):
if remaining == 0:
return 1
return sum(dp(next_d, remaining - 1) for next_d in moves[digit]) % MOD
return sum(dp(d, n - 1) for d in range(10)) % MODO(n)O(n)Precompute valid knight moves from each digit. DP counts paths of length n starting from each digit.
05Minimum Path Cost in a GridMedium
Find minimum cost path from any cell in first row to any cell in last row. moveCost[v][j] is cost to move from value v to column j.
def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
@cache
def dp(i, j):
if i == m - 1:
return grid[i][j]
val = grid[i][j]
return grid[i][j] + min(moveCost[val][k] + dp(i + 1, k) for k in range(n))
return min(dp(0, j) for j in range(n))O(m × n²)O(m × n)From each cell, try all columns in next row. Cost = cell value + move cost + future cost.
06Minimum Cost to Reach Destination in TimeHard
Find minimum cost path from 0 to n-1 within maxTime. Each city has passing fee.
def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
n = len(passingFees)
graph = defaultdict(list)
for u, v, t in edges:
graph[u].append((v, t))
graph[v].append((u, t))
# (cost, time, node)
heap = [(passingFees[0], 0, 0)]
best_time = {0: 0}
while heap:
cost, time, node = heappop(heap)
if node == n - 1:
return cost
for nei, t in graph[node]:
new_time = time + t
if new_time <= maxTime:
if nei not in best_time or new_time < best_time[nei]:
best_time[nei] = new_time
heappush(heap, (cost + passingFees[nei], new_time, nei))
return -1O(E × maxTime × log V)O(V × maxTime)Modified Dijkstra tracking both cost and time. Prune paths exceeding maxTime.
Paint House & Falling Path
Problems involving choosing one option per row with adjacent constraints.
01Paint HouseMedium
Paint n houses with 3 colors. No two adjacent houses same color. Minimize cost.
def minCost(self, costs: List[List[int]]) -> int:
n = len(costs)
@cache
def dp(i, color):
if i == n:
return 0
return costs[i][color] + min(dp(i + 1, c) for c in range(3) if c != color)
return min(dp(0, c) for c in range(3))O(n)O(n)For each house, try all colors except previous house's color. Take minimum.
02Paint House IIHard
Paint n houses with k colors. No two adjacent same color. Minimize cost.
def minCostII(self, costs: List[List[int]]) -> int:
n, k = len(costs), len(costs[0])
@cache
def prefix_min(i, c):
if c < 0: return float('inf')
return min(prefix_min(i, c - 1), dp(i, c))
@cache
def suffix_min(i, c):
if c >= k: return float('inf')
return min(dp(i, c), suffix_min(i, c + 1))
@cache
def dp(i, c):
if i == n: return 0
return costs[i][c] + min(prefix_min(i + 1, c - 1), suffix_min(i + 1, c + 1))
return min(dp(0, c) for c in range(k))O(n × k)O(n × k)O(k²) becomes O(k) using prefix/suffix min. For color c, min of other colors = min(prefix[c-1], suffix[c+1]).
03Paint FenceMedium
Paint n posts with k colors. No three consecutive posts same color. Count ways.
def numWays(self, n: int, k: int) -> int:
if n == 1: return k
@cache
def dp(i, same_as_prev):
if i == n:
return 1
if same_as_prev:
# Must pick different color
return (k - 1) * dp(i + 1, False)
else:
# Can pick same (1 way) or different (k-1 ways)
return dp(i + 1, True) + (k - 1) * dp(i + 1, False)
return k * dp(1, False)O(n)O(n)Track if current matches previous. If two consecutive match, next must differ.
04Minimum Falling Path SumMedium
Find minimum sum path from top row to bottom, moving down/diagonal.
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
n = len(matrix)
@cache
def dp(i, j):
if j < 0 or j >= n:
return float('inf')
if i == n - 1:
return matrix[i][j]
return matrix[i][j] + min(dp(i + 1, j - 1), dp(i + 1, j), dp(i + 1, j + 1))
return min(dp(0, j) for j in range(n))O(n²)O(n²)From each cell, can move to 3 cells below. Take minimum path.
05Minimum Falling Path Sum IIHard
Same as falling path but next row column must be different.
def minFallingPathSum(self, grid: List[List[int]]) -> int:
n, k = len(grid), len(grid[0])
@cache
def prefix_min(i, c):
if c < 0: return float('inf')
return min(prefix_min(i, c - 1), dp(i, c))
@cache
def suffix_min(i, c):
if c >= k: return float('inf')
return min(dp(i, c), suffix_min(i, c + 1))
@cache
def dp(i, c):
if i == n - 1: return grid[i][c]
return grid[i][c] + min(prefix_min(i + 1, c - 1), suffix_min(i + 1, c + 1))
return min(dp(0, c) for c in range(k))O(n × k)O(n × k)Identical to Paint House II. Use prefix/suffix min for O(k) per row instead of O(k²).
06Allocate MailboxesHard
Place k mailboxes to minimize total distance from n houses.
def minDistance(self, houses: List[int], k: int) -> int:
houses.sort()
n = len(houses)
# Cost to serve houses[i:j+1] with one mailbox (place at median)
@cache
def cost(i, j):
if i >= j: return 0
return houses[j] - houses[i] + cost(i + 1, j - 1)
@cache
def dp(i, remaining):
if i == n: return 0
if remaining == 0: return float('inf')
res = float('inf')
for j in range(i, n):
res = min(res, cost(i, j) + dp(j + 1, remaining - 1))
return res
return dp(0, k)O(n² × k)O(n² + n × k)Optimal mailbox for a range is at median. DP partitions houses into k groups.
Game & Jump DP
Problems involving optimal decisions in games or jump sequences.
01Frog JumpHard
Frog crosses river by jumping on stones. If last jump was k, next can be k-1, k, or k+1.
def canCross(self, stones: List[int]) -> bool:
stone_set = set(stones)
target = stones[-1]
@cache
def dp(pos, last_jump):
if pos == target:
return True
for k in [last_jump - 1, last_jump, last_jump + 1]:
if k > 0 and pos + k in stone_set:
if dp(pos + k, k):
return True
return False
return dp(0, 0)O(n²)O(n²)State is (position, last jump). Try all valid next jumps (k-1, k, k+1) that land on stones.
02Minimum Sideway JumpsMedium
3-lane road with obstacles. Minimize sideway jumps to reach end.
def minSideJumps(self, obstacles: List[int]) -> int:
n = len(obstacles)
@cache
def dp(i, lane):
if i == n - 1:
return 0
if obstacles[i + 1] != lane:
return dp(i + 1, lane)
# Must jump sideways
res = float('inf')
for new_lane in [1, 2, 3]:
if new_lane != lane and obstacles[i] != new_lane:
res = min(res, 1 + dp(i, new_lane))
return res
return dp(0, 2) # Start in lane 2O(n)O(n)If next position in current lane is blocked, must jump to unblocked lane. Count jumps.
03Stone Game IIMedium
Alice and Bob take turns taking 1 to 2M piles. M updates to max(M, X). Alice maximizes her stones.
def stoneGameII(self, piles: List[int]) -> int:
n = len(piles)
suffix_sum = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suffix_sum[i] = suffix_sum[i + 1] + piles[i]
@cache
def dp(i, m):
if i >= n:
return 0
if i + 2 * m >= n:
return suffix_sum[i]
min_opponent = float('inf')
for x in range(1, 2 * m + 1):
min_opponent = min(min_opponent, dp(i + x, max(m, x)))
return suffix_sum[i] - min_opponent
return dp(0, 1)O(n³)O(n²)Current player gets suffix_sum - opponent's optimal. Try all valid takes (1 to 2M).
Tree DP
Dynamic programming on tree structures.
01Sum of Distances in TreeHard
Return array where answer[i] is sum of distances from node i to all other nodes.
def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
count = [1] * n # Subtree size
res = [0] * n
# First DFS: compute count and res[0]
def dfs1(node, parent):
for child in graph[node]:
if child != parent:
dfs1(child, node)
count[node] += count[child]
res[0] += res[child] + count[child]
# Second DFS: compute res for all nodes
def dfs2(node, parent):
for child in graph[node]:
if child != parent:
# Moving from node to child:
# count[child] nodes get closer by 1
# n - count[child] nodes get farther by 1
res[child] = res[node] - count[child] + (n - count[child])
dfs2(child, node)
dfs1(0, -1)
dfs2(0, -1)
return resO(n)O(n)Re-rooting technique. First DFS computes answer for root. Second DFS propagates to children using relationship between parent/child answers.
02Kth Ancestor of a Tree NodeHard
Design data structure for efficient kth ancestor queries.
class TreeAncestor:
def __init__(self, n: int, parent: List[int]):
self.LOG = 20
self.up = [[-1] * self.LOG for _ in range(n)]
for i in range(n):
self.up[i][0] = parent[i]
for j in range(1, self.LOG):
for i in range(n):
if self.up[i][j-1] != -1:
self.up[i][j] = self.up[self.up[i][j-1]][j-1]
def getKthAncestor(self, node: int, k: int) -> int:
for j in range(self.LOG):
if k & (1 << j):
node = self.up[node][j]
if node == -1:
return -1
return nodeO(n log n) build, O(log k) queryO(n log n)Binary lifting. up[i][j] = 2^j-th ancestor of i. Query by decomposing k into binary.
03Unique Binary Search TreesMedium
Count structurally unique BSTs with values 1 to n.
def numTrees(self, n: int) -> int:
@cache
def dp(n):
if n <= 1:
return 1
total = 0
for root in range(1, n + 1):
left = root - 1
right = n - root
total += dp(left) * dp(right)
return total
return dp(n)O(n²)O(n)Catalan numbers. For each root i, left subtree has i-1 nodes, right has n-i nodes. Multiply and sum.
04Unique Binary Search Trees IIMedium
Generate all structurally unique BSTs with values 1 to n.
def generateTrees(self, n: int) -> List[TreeNode]:
@cache
def build(lo, hi):
if lo > hi:
return [None]
result = []
for root_val in range(lo, hi + 1):
for left in build(lo, root_val - 1):
for right in build(root_val + 1, hi):
root = TreeNode(root_val)
root.left = left
root.right = right
result.append(root)
return result
return build(1, n)O(4^n / n^1.5)O(4^n / n^1.5)For each root, generate all left/right subtree combinations and connect them.
05Maximize the Number of Target Nodes After Connecting Trees IHard
Connect node i in tree1 to best node in tree2 to maximize nodes within k edges of i.
def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]:
adjList1, adjList2 = defaultdict(list), defaultdict(list)
for u, v in edges1:
adjList1[u].append(v)
adjList1[v].append(u)
for u, v in edges2:
adjList2[u].append(v)
adjList2[v].append(u)
@cache
def dp(i, par, k, tree):
if k < 0: return 0
if k == 0: return 1
res = 1
adj = adjList1[i] if tree else adjList2[i]
for nbr in adj:
if nbr != par:
res += dp(nbr, i, k - 1, tree)
return res
n, m = len(edges1) + 1, len(edges2) + 1
return [max(dp(i, -1, k, True) + dp(j, -1, k - 1, False) for j in range(m)) for i in range(n)]O(n × m × k)O(n × k)For each node i, connect to best j in tree2. Count nodes within k in tree1, k-1 in tree2 (one edge used for connection).
06Unit Conversion IMedium
Given unit conversion graph, find conversion rate from unit 0 to all other units.
def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
n = len(conversions)
MOD = 10**9 + 7
parent = {}
for u, v, w in conversions:
parent[v] = (u, w)
@cache
def dp(i):
if i == 0: return 1
par, w = parent[i]
return (w * dp(par)) % MOD
return [dp(i) for i in range(n + 1)]O(n)O(n)Tree DP from root. Multiply conversion factors along path from unit 0 to each unit.
07Unit Conversion IIMedium
Convert between any two units in conversion tree.
def queryConversions(self, conversions: List[List[int]], queries: List[List[int]]) -> List[int]:
n = len(conversions)
MOD = 10**9 + 7
parent = {}
for u, v, w in conversions:
parent[v] = (u, w)
@cache
def dp(i):
if i == 0: return 1
par, w = parent[i]
return (w * dp(par)) % MOD
return [(pow(dp(a), -1, MOD) * dp(b)) % MOD for a, b in queries]O(n + q)O(n)Convert A→B = dp(B) / dp(A) using modular inverse. dp(i) is rate from unit 0 to i.
08Maximum Weighted K-Edge PathMedium
Find max sum path with exactly k edges in DAG, sum must be < t.
def maxWeight(self, n: int, edges: List[List[int]], k: int, t: int) -> int:
adjList = defaultdict(list)
for u, v, w in edges:
adjList[u].append((v, w))
@cache
def dp(i, k):
if k == 0: return {0}
res = set()
for nbr, w in adjList[i]:
for nbr_sum in dp(nbr, k - 1):
if w + nbr_sum < t:
res.add(w + nbr_sum)
return res
res = -1
for i in range(n):
for path_sum in dp(i, k):
if path_sum < t:
res = max(res, path_sum)
return resO(E × k × t)O(n × k × t)Track all possible sums for paths of length k from each node. Use set to collect valid sums < t.
09Subtree Inversion SumHard
Maximize tree sum by inverting subtrees (multiply by -1), with min distance k between inversions.
def subtreeInversionSum(self, edges: List[List[int]], nums: List[int], k: int) -> int:
adjList = defaultdict(list)
for u, v in edges:
adjList[u].append(v)
adjList[v].append(u)
@cache
def dp(root, par, dist, odd):
no_invert = -nums[root] if odd else nums[root]
invert = -nums[root] if not odd and dist >= k else nums[root]
for nbr in adjList[root]:
if nbr == par: continue
no_invert += dp(nbr, root, dist + 1, odd)
if dist >= k:
invert += dp(nbr, root, 1, not odd)
return max(no_invert, invert) if dist >= k else no_invert
return dp(0, -1, float('inf'), False)O(n × k)O(n × k)Track distance since last inversion and parity (odd = currently inverted). Can only invert if dist >= k.
10Minimum Weighted Subgraph With the Required Paths IIHard
Find min weight subtree connecting src1, src2, and dest for each query.
def minimumWeight(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
from collections import defaultdict
n = len(edges) + 1
LOG = (n - 1).bit_length()
tree = defaultdict(list)
for u, v, w in edges:
tree[u].append((v, w))
tree[v].append((u, w))
parent = [[-1] * n for _ in range(LOG)]
depth, dist = [0] * n, [0] * n
def dfs(u, p):
for v, w in tree[u]:
if v != p:
parent[0][v] = u
depth[v] = depth[u] + 1
dist[v] = dist[u] + w
dfs(v, u)
dfs(0, -1)
for k in range(1, LOG):
for v in range(n):
if parent[k-1][v] != -1:
parent[k][v] = parent[k-1][parent[k-1][v]]
def lca(u, v):
if depth[u] < depth[v]: u, v = v, u
diff = depth[u] - depth[v]
for k in range(LOG):
if diff & (1 << k): u = parent[k][u]
if u == v: return u
for k in range(LOG - 1, -1, -1):
if parent[k][u] != parent[k][v]:
u, v = parent[k][u], parent[k][v]
return parent[0][u]
def path_dist(u, v):
return dist[u] + dist[v] - 2 * dist[lca(u, v)]
res = []
for s1, s2, d in queries:
l12, l1d, l2d = lca(s1, s2), lca(s1, d), lca(s2, d)
meet = max([l12, l1d, l2d], key=lambda x: depth[x])
res.append(path_dist(s1, meet) + path_dist(s2, meet) + path_dist(d, meet))
return resO(n log n + q log n)O(n log n)Binary lifting for LCA. Min subtree connecting 3 nodes meets at the deepest pairwise LCA.
More Bitmask DP
Additional bitmask DP problems.
01Partition to K Equal Sum SubsetsMedium
Partition array into k subsets with equal sum.
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
total = sum(nums)
if total % k != 0:
return False
target = total // k
n = len(nums)
@cache
def dp(mask, curr_sum):
if mask == (1 << n) - 1:
return True
for i in range(n):
if not (mask & (1 << i)) and curr_sum + nums[i] <= target:
next_sum = (curr_sum + nums[i]) % target
if dp(mask | (1 << i), next_sum):
return True
return False
return dp(0, 0)O(n × 2^n)O(2^n)Bitmask tracks used elements. curr_sum resets to 0 when reaching target (completed one subset).
02Maximize Score After N OperationsHard
Perform n operations, each picking 2 elements with score = op_num × gcd(x, y).
def maxScore(self, nums: List[int]) -> int:
m = len(nums)
n = m // 2
@cache
def dp(mask):
op = 1 + bin(mask).count('1') // 2
if op > n:
return 0
ans = 0
for i in range(m):
if mask & (1 << i): continue
for j in range(i + 1, m):
if mask & (1 << j): continue
new_mask = mask | (1 << i) | (1 << j)
score = op * math.gcd(nums[i], nums[j]) + dp(new_mask)
ans = max(ans, score)
return ans
return dp(0)O(n² × 2^n)O(2^n)Try all pairs of unused elements. Operation number derived from bit count.
03Number of Ways to Wear Different Hats to Each OtherHard
n people, 40 hats. Each person has preference list. Count valid assignments.
def numberWays(self, hats: List[List[int]]) -> int:
MOD = 10 ** 9 + 7
n = len(hats)
# Invert: for each hat, which people can wear it
hat_to_people = defaultdict(list)
for person, hat_list in enumerate(hats):
for hat in hat_list:
hat_to_people[hat].append(person)
@cache
def dp(hat, mask):
if mask == (1 << n) - 1:
return 1
if hat > 40:
return 0
# Don't use this hat
res = dp(hat + 1, mask)
# Assign this hat to someone who wants it and isn't assigned
for person in hat_to_people[hat]:
if not (mask & (1 << person)):
res = (res + dp(hat + 1, mask | (1 << person))) % MOD
return res
return dp(1, 0)O(40 × n × 2^n)O(40 × 2^n)Iterate over hats (40), mask tracks assigned people (n ≤ 10). Invert the problem for smaller state space.
04Find the Shortest SuperstringHard
Find shortest string containing all given strings as substrings.
def shortestSuperstring(self, words: List[str]) -> str:
n = len(words)
# Precompute overlap[i][j] = max overlap when words[i] followed by words[j]
overlap = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i != j:
for k in range(min(len(words[i]), len(words[j])), 0, -1):
if words[i][-k:] == words[j][:k]:
overlap[i][j] = k
break
@cache
def dp(mask, last):
if mask == (1 << n) - 1:
return ""
best = None
for i in range(n):
if not (mask & (1 << i)):
suffix = words[i][overlap[last][i]:] if last != -1 else words[i]
candidate = suffix + dp(mask | (1 << i), i)
if best is None or len(candidate) < len(best):
best = candidate
return best
return dp(0, -1)O(n² × 2^n)O(n × 2^n)TSP-like. Precompute overlaps. DP finds optimal ordering to minimize total non-overlapping length.
05Maximum Students Taking ExamHard
Place students in seats (avoiding cheating) to maximize count. Can't see diagonally adjacent.
def maxStudents(self, seats: List[List[str]]) -> int:
m, n = len(seats), len(seats[0])
def valid_row(row_idx, mask):
for j in range(n):
if mask & (1 << j):
if seats[row_idx][j] == '#':
return False
if j > 0 and (mask & (1 << (j - 1))):
return False
return True
def compatible(prev_mask, curr_mask):
for j in range(n):
if curr_mask & (1 << j):
if j > 0 and (prev_mask & (1 << (j - 1))):
return False
if j < n - 1 and (prev_mask & (1 << (j + 1))):
return False
return True
@cache
def dp(row, prev_mask):
if row == m:
return 0
best = 0
for mask in range(1 << n):
if valid_row(row, mask) and compatible(prev_mask, mask):
best = max(best, bin(mask).count('1') + dp(row + 1, mask))
return best
return dp(0, 0)O(m × 4^n)O(m × 2^n)Row-by-row DP. Check each row configuration is valid (no broken seats, no adjacent) and compatible with previous row.
06Number of Ways to Build Sturdy Brick WallHard
Build wall of given height and width using bricks. Adjacent rows must not have brick edges at same position.
def buildWall(self, height: int, width: int, bricks: List[int]) -> int:
MOD = 10**9 + 7
@cache
def dp(i, j, curr_mask, prev_mask):
if i == height: return 1
if j == width: return dp(i + 1, 0, 0, curr_mask)
res = 0
for b in bricks:
if j + b <= width and (prev_mask & (1 << (j + b))) == 0:
new_mask = curr_mask | (1 << (j + b)) if j + b < width else curr_mask
res = (res + dp(i, j + b, new_mask, prev_mask)) % MOD
return res
return dp(0, 0, 0, 0)O(height × width × 2^width × bricks)O(height × width × 4^width)Track brick edges as bitmask. Current row edges can't align with previous row edges. Don't mark final edge at width.
07Minimum Time to Kill All MonstersHard
Kill monsters with increasing mana gain. Find minimum days to kill all.
def minimumTime(self, power: List[int]) -> int:
from math import ceil
n = len(power)
@cache
def dp(mask):
dead = bin(mask).count('1')
gain = dead + 1
if dead == n: return 0
return min(ceil(power[i] / gain) + dp(mask | (1 << i))
for i in range(n) if not (mask & (1 << i)))
return dp(0)O(n × 2^n)O(2^n)Gain increases with each kill, so order matters. Bitmask tracks killed monsters. Derive gain from popcount.
More Digit DP
Additional digit DP problems.
01Number of Beautiful Integers in the RangeHard
Count integers in [low, high] with equal odd/even digits and divisible by k.
def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
def count(num):
s = str(num)
n = len(s)
@cache
def dp(i, tight, started, diff, mod):
if i == n:
return 1 if started and diff == 0 and mod == 0 else 0
limit = int(s[i]) if tight else 9
res = 0
for d in range(0, limit + 1):
new_tight = tight and (d == limit)
new_started = started or (d > 0)
if not new_started:
res += dp(i + 1, new_tight, False, 0, 0)
else:
new_diff = diff + (1 if d % 2 == 1 else -1)
new_mod = (mod * 10 + d) % k
res += dp(i + 1, new_tight, True, new_diff, new_mod)
return res
return dp(0, True, False, 0, 0)
return count(high) - count(low - 1)O(n × k × n)O(n × k × n)Track: position, tight bound, started, odd-even diff, remainder mod k. Count in [0, high] - [0, low-1].
02Count Numbers with Non-Decreasing DigitsHard
Count integers in [l, r] with non-decreasing digits.
def countNumbers(self, l: str, r: str) -> int:
MOD = 10 ** 9 + 7
def count(s):
n = len(s)
@cache
def dp(i, tight, started, last_digit):
if i == n:
return 1 if started else 0
limit = int(s[i]) if tight else 9
res = 0
start = last_digit if started else 0
for d in range(start, limit + 1):
new_tight = tight and (d == limit)
new_started = started or (d > 0)
new_last = d if new_started else 0
res = (res + dp(i + 1, new_tight, new_started, new_last)) % MOD
return res
return dp(0, True, False, 0)
def subtract_one(s):
s = list(s)
i = len(s) - 1
while i >= 0 and s[i] == '0':
s[i] = '9'
i -= 1
s[i] = str(int(s[i]) - 1)
return ''.join(s).lstrip('0') or '0'
return (count(r) - count(subtract_one(l)) + MOD) % MODO(n × 10)O(n × 10)Standard digit DP with last_digit constraint. Digits must be >= previous digit.
More Interval DP
Additional interval/scheduling DP problems.
01Maximum Number of Events That Can Be Attended IIHard
Attend at most k events (non-overlapping) to maximize total value.
def maxValue(self, events: List[List[int]], k: int) -> int:
events.sort()
n = len(events)
@cache
def dp(i, remaining):
if i == n or remaining == 0:
return 0
# Skip this event
res = dp(i + 1, remaining)
# Attend this event - find next non-overlapping
end = events[i][1]
j = bisect_left(events, [end + 1, 0, 0])
res = max(res, events[i][2] + dp(j, remaining - 1))
return res
return dp(0, k)O(n × k × log n)O(n × k)Sort by start time. For each event, binary search for next non-overlapping event.
02Two Best Non-Overlapping EventsMedium
Attend at most 2 non-overlapping events to maximize total value.
def maxTwoEvents(self, events: List[List[int]]) -> int:
events.sort()
n = len(events)
# Suffix max value
suffix_max = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suffix_max[i] = max(events[i][2], suffix_max[i + 1])
res = 0
for i in range(n):
# Take only this event
res = max(res, events[i][2])
# Take this event + best non-overlapping
end = events[i][1]
j = bisect_left(events, [end + 1, 0, 0])
if j < n:
res = max(res, events[i][2] + suffix_max[j])
return resO(n log n)O(n)Precompute suffix max values. For each event, find best event starting after it ends.
03Maximize Win From Two SegmentsMedium
Choose two non-overlapping segments of length k to maximize covered prizes.
def maximizeWin(self, prizePositions: List[int], k: int) -> int:
n = len(prizePositions)
# best[i] = max prizes from one segment ending at or before position i
best = [0] * (n + 1)
res = 0
left = 0
for right in range(n):
while prizePositions[right] - prizePositions[left] > k:
left += 1
count = right - left + 1
best[right + 1] = max(best[right], count)
res = max(res, count + best[left])
return resO(n)O(n)Sliding window + prefix max. For each right endpoint, combine with best segment ending before left.
04Best Time to Buy and Sell Stock IIIHard
Maximum profit with at most 2 transactions.
def maxProfit(self, prices: List[int]) -> int:
@cache
def dp(i, k, holding):
if i == len(prices) or k == 0:
return 0
if holding:
return max(dp(i + 1, k, True), dp(i + 1, k - 1, False) + prices[i])
else:
return max(dp(i + 1, k, False), dp(i + 1, k, True) - prices[i])
return dp(0, 2, False)O(n)O(n)Special case of k transactions where k=2. Track remaining transactions and holding state.
More LIS Variants
Additional Longest Increasing Subsequence variants.
01Length of Longest Fibonacci SubsequenceMedium
Find longest subsequence where each element is sum of previous two.
def lenLongestFibSubseq(self, arr: List[int]) -> int:
index = {x: i for i, x in enumerate(arr)}
n = len(arr)
@cache
def dp(i, j):
# Length of fib sequence ending with arr[i], arr[j]
target = arr[j] - arr[i]
if target < arr[i] and target in index:
return dp(index[target], i) + 1
return 2
res = 0
for j in range(n):
for i in range(j):
res = max(res, dp(i, j))
return res if res >= 3 else 0O(n²)O(n²)dp(i, j) = length of Fibonacci sequence ending at indices i, j. Previous element must be arr[j] - arr[i].
02The Number of Weak Characters in the GameMedium
Count characters where both attack and defense are strictly less than another character.
def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
# Sort by attack desc, then defense asc
properties.sort(key=lambda x: (-x[0], x[1]))
res = 0
max_defense = 0
for attack, defense in properties:
if defense < max_defense:
res += 1
max_defense = max(max_defense, defense)
return resO(n log n)O(1)Sort by attack descending, defense ascending. Track max defense seen. A character is weak if its defense < max_defense.
03Length of the Longest Increasing PathHard
Find longest path visiting coordinates in strictly increasing order by both x and y.
def maxPathLength(self, coordinates: List[List[int]], k: int) -> int:
n = len(coordinates)
kx, ky = coordinates[k]
# Split into before k and after k
before = [(x, y) for x, y in coordinates if x < kx and y < ky]
after = [(x, y) for x, y in coordinates if x > kx and y > ky]
def lis_2d(points):
if not points:
return 0
points.sort(key=lambda p: (p[0], -p[1]))
from sortedcontainers import SortedList
sl = SortedList()
for x, y in points:
idx = sl.bisect_left(y)
if idx < len(sl):
sl.pop(idx)
sl.add(y)
return len(sl)
return 1 + lis_2d(before) + lis_2d(after)O(n log n)O(n)Split points into before/after k. Find 2D LIS in each part using sort + patience sort on y-values.