Dynamic Programming
Leetcode DP study plan list II
- Day 1 Basics of Dynamic Programming
- Day 2 One Dimensional Dynamic Programming
- Day 3 One Dimensional Dynamic Programming
- Day 4 One Dimensional Dynamic Programming
- Day 5 One Dimensional Dynamic Programming
- Day 6 One Dimensional Dynamic Programming
- Day 7 Dynamic Programming on String
- Day 8 Dynamic Programming on String
- Day 9 Dynamic Programming on String
- Day 10 Dynamic Programming on String
- Day 11 Dynamic Programming on String
- Day 12 Dynamic Programming on String
- Day 13 Min/Max Path Sum
- Day 14 Classic Dynamic Programming Problems
- 343. Integer Break
- 238. Product of Array Except Self # not really
- Day 15 Memoization
- 139. Word Break
- 254. Factor Combinations
- 329. Longest Increasing Path in a Matrix # google follow up return path rather than length
- Day 16 Unique Paths
- Out of Boundary Paths
- Unique Binary Search Trees
- Day 19 Coin Change / Combination Sum
- Day 20 Coin Change / Combination Sum
- Day 21 Partition Equal Subset Sum
Leetcode DP study plan list III
- Day 1 Classic Dynamic Programming Problems
- Day 2 One Dimensional Dynamic Programming
- Day 3 One Dimensional Dynamic Programming
- Day 4 One Dimensional Dynamic Programming
- Day 5 Dynamic Programming on String
- 115. Distinct Subsequences
- 435. Non-overlapping Intervals # greedy really
- Day 6 Dynamic Programming on String
- Day 7 Dynamic Programming on String
- Day 8 Dynamic Programming on String
- Day 9 Dynamic Programming on String
- Day 10 Min/Max Path Sum
- Day 11 Memoization
- 140. Word Break II # backtracking
- 351. Android Unlock Patterns
- Day 12 Dynamic Programming on Counting
- Day 13 Dynamic Programming on Counting
- Day 14 Dynamic Programming on Counting
- Day 15 Merge Interval
- Day 16 Coin Change / Combination Sum
- Day 17 Backpack questions
- Day 18 Dynamic Programming on Game Theory
- Day 19 Dynamic Programming on Game Theory
- Day 20 Bit Manipulation
- Day 21 Dynamic Programming on Numbers
- Day 22 Dynamic Programming on Tree
- Day 23 Dynamic Programming on Tree
Climb Stairs / Jump Games
70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Thought process
- This is exactlly the fibonacci number question.
- Let
dp[i]be the number of ways we can get to ith step. - Then
dp[i] = dp[i - 1] + dp[i - 2]since we can either go 1 step up from i - 1 or 2 steps up from i - 2.
def climb_stairs(n):
current, prev = 1, 1
for _ in range(1, n):
current, prev = current + prev, current
return current
746. Min Cost Climbing Stairs
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Thought process:
- Whenever we are at ith step, no matter 1 or 2 steps we move up, we have to pay the cost of
cost[i]. - So let
dp[i]be the minimal cost we will pay to get to i and move on. dp[i - 1]will be the min cost to get to i from 0 through stepping one step up from i - 1.dp[i - 2]will be the min cost to get to i from 0 through stepping two steps up from i - 2.- The transition formula is:
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i].
def min_cost_climbing_stairs(cost):
prev, curr = cost[:2]
for i, c in enumerate(cost[2:], 2):
prev, curr = curr, min(prev, curr) + c
return min(prev, curr)
55. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
Thought process:
- Let
dp[i]indicates whether we can reach the end from location i, obviouslydp[-1] = True. - We work from right to left, mark
dp[j]to be True if any of the locations we can jump to from j is True. dp[0]tells us whether we can reach the end from location 0.
def jump(nums):
n = len(nums)
dp = [0] * len(nums)
dp[-1] = 1
for i in range(n - 2, -1, -1):
step = nums[i]
reach = min(i + step, n - 1)
if any(dp[j] for j in range(i, reach + 1)): dp[i] = 1
return dp[0]
Thought process:
- The above procedure is not efficient, as we would need to check a range of values at each step. The
dptable stores only binary information. - We can put more info in the
dptable and reduce the range scan at each step. - Let
dp[i]be the furtherest step we can get to from i, it is the maximum betweendp[i - 1]andi + nums[i]. - We pad the dp table with one
1at the left, since we always can get to the first position.
def jump(nums):
dp = [1] + [0] * len(nums)
for i, num in enumerate(nums, 1):
if i > dp[i - 1]: return False
dp[i] = max(i + num, dp[i - 1])
return True
Now notice the dp transition formula is just take the maximum between two quantities, one is calculated at i and one is the previous result, we can simplify the code to use constant space:
def jump(nums):
prev = 0
for i, num in enumerate(nums):
if i > prev: return False
prev = max(prev, i + num)
return True
45. Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array. cEach element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.
Thought process:
- Let
dp[i]be the number of jumps we need to get to the end. - We initialize everything to be infinity except 1 for the end(Since we need at least 1 jump to get to the end).
- We populate the table from right to left.
- The transition formula is
dp[i] = min(dp[j] for j in reachable positions from j) + 1 dp[0]is what we need.
def jump(nums):
n = len(nums)
dp = [float('inf')] * len(nums)
dp[-1] = 0
for i in range(n - 2, -1, -1):
step = nums[i]
reach = min(i + step, n - 1)
dp[i] = min(dp[i: reach + 1]) + 1
return dp[0]
Thought process:
- Same rational as with the Jump Game problem, we can have \(O(n)\) solution.
def jump(nums):
dp = [0] * len(nums)
nxt = 0
num_steps = 0
for i, num in enumerate(nums):
if i > nxt:
num_steps += 1
nxt = dp[i - 1]
dp[i] = max(i + num, dp[i - 1])
return num_steps
Same rational as above, we can reduce the space usage to constant.
def jump(nums):
prev, nxt, num_steps = 0, 0, 0
for i, num in enumerate(nums):
if i > prev:
prev = nxt
num_steps += 1
nxt = max(nxt, i + num)
return num_steps
Knapsack
The two dimensions of the dp table typically represents:
- items to take.
- capacity / target.
- where the cell value is something like the max value we can get with the items not exceeding the capacity.
- the solution to the question typicall be the last cell in the table.
- depends on the problem, the 2D table may be simplified to 1D.
416. Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Thought process:
- Find a partition of two subsets with equal sum is equivalent to find one subset sum up to half of the overall sum.
- Use dp to find it out.
- The elements in 2D table dp[i][j] means with the first i - 1 numbers from the set can I use them to sum up to j.
- Let n be the number of integers in set and s be the sum of the set, the dp table is of size n by s // 2 + 1.
- \(+1\) for that we padded left with 0, since we can always choose to not add anything to sum up to zero.
def can_partition(nums):
s = sum(nums)
if s % 2: return False
s //= 2
n = len(nums)
dp = [[True] + [False] * s for _ in range(n)]
if nums[0] <= s: dp[0][nums[0]] = True
for i, num in enumerate(nums[1:], 1):
for j in range(1, s + 1):
if dp[i - 1][j]:
dp[i][j] = True
elif j >= num:
dp[i][j] = dp[i - 1][j - num]
return dp[-1][-1]
494. Target Sum
You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Thought process
- Let \(f(i, s)\) be the number of ways we can assign symbols to make sum of first \(i\) numbers sum to \(s\). So we want return \(f(n, S)\) in the end.
- The transition formula is \(f(i, s) = f(i - 1, s - a_i) + f(i - 1, s + a_i)\).
- And the basecase is \(f(0, 0) = 1\)
- Note we can do this in a breadth first search fashion, and once we move to \(f(i, ?)\) we can discard saved results for \(f(i - 2, ?)\)
def target_sum(nums, S):
if not nums: return 0
level = defaultdict(int)
level[0] = 1
for num in nums:
next_level = defaultdict(int)
for val in level:
next_level[val + num] += level[val]
next_level[val - num] += level[val]
level = next_level
return level[S]
879. Profitable Schemes
class Solution:
def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
dp = [[0] * (n + 1) for i in range(minProfit + 1)]
dp[0][0] = 1
for p, g in zip(profit, group):
for i in reversed(range(minProfit + 1)):
for j in reversed(range(n - g + 1)):
dp[min(i + p, minProfit)][j + g] += dp[i][j]
return sum(dp[minProfit]) % (10**9 + 7)
322. Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Thought process:
- Let \(f(a)\) be the minimal number of coins needed to sum up to amount \(a\)
- The transition formula is \(f(a) = min({f(a - c) for c in coin_values}) + 1\)
def coin_change(coins, amount):
min_coin = min(coins)
dp = [0] + [float('inf')] * amount
for amt in range(amount + 1):
if amt < min_coin: continue
dp[amt] = min({dp[amt - c] for c in coins if amt >= c}) + 1
return dp[amount] if dp[amount] != float('inf') else -1
518. Coin Change 2
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Thought process:
def change(amount, coins):
dp = [1] + [0] * amount
for c in coins:
for amt in range(c, amount + 1):
dp[amt] += dp[amt - c]
return dp[amount]
1235. Maximum Profit in Job Scheduling
INF = 2 ** 32
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
jobs = sorted([(e,s,p) for s, e, p in zip(startTime, endTime, profit)])
dp = [[0, 0]] # end time and max_profit
for e, s, p in jobs:
prev = bisect.bisect_right(dp, [s, INF]) - 1
if dp[prev][1] + p > dp[-1][1]:
dp.append([e, dp[prev][1] + p])
return dp[-1][1]
1751. Maximum Number of Events That Can Be Attended II
class Solution:
def maxValue(self, events: List[List[int]], K: int) -> int:
events.sort(key=lambda x: x[1])
dp, ndp = [[0, 0]], [[0, 0]]
for k in range(K):
for s, e, v in events:
i = bisect.bisect_left(dp, [s]) - 1
if dp[i][1] + v > ndp[-1][1]:
ndp.append([e, dp[i][1] + v])
dp, ndp = ndp, [[0, 0]]
return dp[-1][-1]
Buy and Sell Stock
123. Best Time to Buy and Sell Stock III
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
# action buy sell idle
# states init bought 1 sold 1 bought 2 sold 2
# state transition
#
# |--- |----- |------ |----- |-----
# V idle V idle V idle V idle V idle
# init -buy-> 1st buy ---------sell---->sold 1st------buy-> 2nd buy-----------sell-------->sold 2nd
#
# immediate sell will result gain 0, which is equal to idle.
INT_MIN = -2 ** 32
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# init, bought 1, sold 1, bought 2, sold 2
states = [0, INT_MIN, 0, INT_MIN, 0] # amt of money at each state.
for price in prices:
i, b1, s1, b2, s2 = states
b1 = max(b1, i - price) # idle or init-buy->b1; buy cheap
s1 = max(s1, price + b1) # idle or b1-sell->s1; sell high
b2 = max(b2, s1 - price) # idle or s1-buy->b2; buy cheap
s2 = max(s2, price + b2) # idle or b2-sell->s2; sell high
states = [i, b1, s1, b2, s2]
return s2
188. Best Time to Buy and Sell Stock IV
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Extend 123 solution to k bought and k sold states
INT_MIN = -2 ** 32
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
dp = [[0, 0]] + [[INT_MIN, 0] for _ in range(k)]
for price in prices:
for i in range(1, k+1):
dp[i][0] = max(dp[i][0], dp[i-1][1] - price)
dp[i][1] = max(dp[i][1], price + dp[i][0])
return dp[k][1]
Math, Geometry
1259. Handshakes That Don’t Cross
Consider connect people 1 with people i in (2, 4, 6, …) which seperate the people into two groups of size (i - 2) and (n - i). Each group is a problem of a smaller size and should be multiplied and summed over i to answer the current problem.
MOD = 10**9 + 7
class Solution:
def numberOfWays(self, numPeople: int) -> int:
@cache
def f(n):
if n == 0: return 1
total = 0
for i in range(2, n + 1, 2):
total += f(i - 2) * f(n - i)
total %= MOD
return total
return f(numPeople)
1478. Allocate Mailboxes
- Double DP!!!!
- First 2D DP to solve the cost to put one mailbox to minimize total distance from [i: j] both inclusive
- dp1[i,j] be the mincost to use one mailbox for house i to house j
- dp1[i,j] = 0 if i == j
- dp1[i,j] = xj- xi if j == i + 1
- dp1[i,j] = dp1[i+1,j-1] + xj-xi otherwise
- Then 2D DP to solve the minimal cost when k mailboxes are allowed
- dp2[i,k] be the cost to use k mailbox for house 0 to house i
- dp2[i,k] = min(dp2[j,k-1] + dp1[j+1,i]) for all j in range(0, i).
class Solution:
def minDistance(self, houses: List[int], k: int) -> int:
houses.sort()
n = len(houses)
@cache
def get_cost(i, j):
if i == j: return 0
if j == i + 1: return houses[j] - houses[i]
return get_cost(i+1, j-1) + houses[j] - houses[i]
@cache
def dp(i, k):
if k > i: return 0
if k == 1: return get_cost(0, i)
return min(dp(p, k-1) + get_cost(p+1, i) for p in range(i))
return dp(n-1, k)
(Sub) Sequence / string matching
115. Distinct Subsequences
prefix both s and t with space. f(i, j) = # matches using s[:j] against t[:i] (inclusive) f(i, j) = f(i, j-1) + I[s[j] == t[i]] * f(i-1, j-1)
class Solution:
def numDistinct(self, s: str, t: str) -> int:
dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]
dp[0] = [1] * (len(s) + 1)
for i in range(1, len(t) + 1):
for j in range(i, len(s) + 1):
dp[i][j] = dp[i][j-1] + int(bool(t[i-1] == s[j-1])) * dp[i-1][j-1]
return dp[-1][-1]
1682. Longest Palindromic Subsequence II
Expansion? f(i, j) length of the longest good palindromic subsequence, last matched character f(i, j) = f(i+1, j-1) + 2, s[i] if s[i] == s[j] and s[i] != last_used = max(f(i+1, j), f(i, j-1))
class Solution:
def solution_top_down(self, s):
n = len(s)
@cache
def f(i, j):
if i >= j: return 0, ""
if s[i] == s[j] and s[i] != f(i+1,j-1)[1]: return 2 + f(i+1, j-1)[0], s[i]
return max(f(i+1, j), f(i, j-1))
return f(0, n -1)[0]
def solution_bottom_up(self, s):
n = len(s)
dp = [[[0, ""]] * n for _ in range(n) ]
for d in range(1, n):
i, j = 0, d
while 0 <= i < j < n:
if s[i] == s[j] and s[i] != dp[i+1][j-1][1]:
dp[i][j] = [dp[i+1][j-1][0] + 2, s[i]]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
i += 1; j += 1
return dp[0][n-1][0]
longestPalindromeSubseq = solution_bottom_up
1062. Longest Repeating Substring
Also see 1044.
class Solution:
def solution_binary_search(self, S: str) -> int:
D = [ord(c) - ord('a') for c in S]
P = 26
MOD = 10 ** 9 + 7
def rolling_hash(L):
# initial window
h = 0
for c in D[:L]: h = (h * P + c) % MOD
seen = defaultdict(list)
seen[h].append(0)
PP = P ** L % MOD
# sliding window
for r, c in enumerate(D[L:], L):
# update window
# shift left emit the old left adding the new right
h = (h * P - D[r - L] * PP + c) % MOD
# collision detection
if h in seen:
if any(S[start:start + L] == S[r-L+1:r+1] for start in seen[h]): return True
seen[h].append(r-L+1)
return False
l, h = 1, len(S)
while l < h:
m = (l + h) >> 1
if rolling_hash(m): # find l such that rolling_hash[l:] == False
l = m +1
else:
h = m
return l - 1
longestRepeatingSubstring = solution_binary_search
516. Longest Palindromic Subsequence
class Solution:
def solution_2d_bottm_up(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)] # dp[l][r] is longest palindrom sub seq of s[l:r+1)
for r in range(n):
dp[r][r] = 1
for l in range(r-1, -1, -1):
if s[l] == s[r]:
dp[l][r] = 2 + dp[l+1][r-1]
else:
dp[l][r] = max(dp[l+1][r], dp[l][r-1])
return dp[0][~0]
def solution_1d_bottm_up(self, s: str) -> int:
# compress to use two alternating rows
n = len(s)
prev = [0] * n
for r in range(n):
curr = [0] * n
curr[r] = 1
for l in range(r-1, -1, -1):
if s[l] == s[r]:
curr[l] = 2 + prev[l+1]
else:
curr[l] = max(curr[l+1], prev[l])
prev = curr
return curr[0]
longestPalindromeSubseq = solution_1d_bottm_up # solution_2d_bottm_up
1216. Valid Palindrome III
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
return len(s) - self.longestPalindromeSubseq(s) <= k
741. Cherry Pickup
class Solution:
def solution_dp_topdown(self, grid):
n = len(grid)
memo = dict()
def dp(r1, c1, r2, c2):
key = (r1, c1, r2, c2)
if n in key or grid[r1][c1] == -1 or grid[r2][c2] == -1: return float('-inf')
if r1 == c1 == n-1: return grid[r1][c1]
if key in memo: return memo[key]
total = grid[r1][c1] + int(c1 != c2) * grid[r2][c2]
total += max(
dp(r1, c1+1, r2, c2+1),
dp(r1, c1+1, r2+1, c2),
dp(r1+1, c1, r2, c2+1),
dp(r1+1, c1, r2+1, c2)
)
memo[key] = total
return memo[key]
return max(0, dp(0, 0, 0, 0))
def solution_dp_bottmup(self, grid: List[List[int]]) -> int:
n = len(grid)
dp = [[-1] * n for _ in range(n)]
dp[0][0] = grid[0][0]
for t in range(1, 2*n-1):
dp2 = [[-1] * n for _ in range(n)]
for i in range(max(0, t-(n-1)), min(n-1, t) + 1):
for j in range(max(0, t-(n-1)), min(n-1, t)+1):
if grid[i][t-i] == -1 or grid[j][t-j] == -1: continue
val = grid[i][t-i]
if i != j: val += grid[j][t-j]
dp2[i][j] = max(dp[pi][pj] + val
for pi in (i-1,i)
for pj in (j-1,j)
if pi >=0 and pj >= 0
)
dp = dp2
return max(0, dp[~0][~0])
cherryPickup = solution_dp_topdown
1463. Cherry Pickup II
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
nrow, ncol = len(grid), len(grid[0])
dp = defaultdict(lambda: -1)
dp[(0,0,ncol-1)] = grid[0][0] + grid[0][ncol-1]
max_val = grid[0][0] + grid[0][ncol-1]
for r in range(1, len(grid)):
for i, j in product(range(ncol), repeat=2):
options = [
dp[(r-1, i+di, j+dj)]
for di, dj in product([-1, 0, 1], repeat=2)
]
max_option = max(options)
if max_option == -1:
dp[(r, i, j)] = -1
else:
dp[(r, i, j)] = max_option + grid[r][i] + int(i != j) * grid[r][j]
max_val = max(max_val, dp[(r, i, j)])
return max_val
688. Knight Probability in Chessboard
class Solution:
def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
probs = [[0] * n for _ in range(n)]
probs[row][column] = 1
while k:
n_probs = [[0] * n for _ in range(n)]
for r, c in product(range(n), repeat=2):
if not probs[r][c]: continue
prob = probs[r][c]
for nr, nc in ((r-2,c+1), (r-1,c+2), (r+1,c+2), (r+2,c+1),
(r+2,c-1), (r+1,c-2), (r-1,c-2), (r-2,c-1)):
if not (0 <= nr < n and 0 <= nc < n): continue
n_probs[nr][nc] += prob / 8
probs = n_probs
k -= 1
return sum(sum(row) for row in probs)
750. Number Of Corner Rectangles
class Solution:
def countCornerRectangles(self, grid):
nrow, ncol = len(grid), len(grid[0])
count = Counter()
total = 0
for r in range(nrow):
for c1 in range(ncol):
if grid[r][c1] == 0: continue
for c2 in range(c1 + 1, ncol):
if grid[r][c2] == 0: continue
total += count[c1, c2]
count[c1, c2] += 1
return total
651. 4 Keys Keyboard
class Solution:
def maxA(self, n: int) -> int:
@cache
def dp(i):
if i <= 3: return i
val = dp(i-1) + 1
for j in range(1, i - 2):
val = max(val, dp(j) * (i - j - 1))
return val
return dp(n)
def maxA(self, n):
dp = [0] * (n + 1)
dp[:4] = [0,1,2,3]
for i in range(4, n+1):
dp[i] = dp[i-1] + 1
for j in range(1, i - 2):
dp[i] = max(dp[i], dp[j] * (i - j - 1))
return dp[n]
634. Find the Derangement of An Array
class Solution:
def findDerangement(self, n: int) -> int:
MOD = 1_000_000_007
if n == 0: return 1
if n == 1: return 0
prev, curr = 1, 0
for i in range(2, n+1):
prev, curr = curr, ((i - 1) * (prev + curr)) % MOD
return curr
1692. Count Ways to Distribute Candies
- DP
- dp[i][j] = (dp[i-1][j] * j + dp[i-1][j-1])
MOD = 1_000_000_007
class Solution:
def waysToDistribute(self, n: int, k: int) -> int:
# @cache
# def dp(i, j):
# if j < 0 or i < j: return 0
# if i == j: return 1
# return (dp(i-1, j) * j + dp(i-1, j-1)) % MOD
# return dp(n, k)
# dp = [[0] * (k+1) for _ in range(n+1)]
# for i in range(k): dp[i][i] = 1
# for i in range(1, n + 1):
# for j in range(1, k+1):
# dp[i][j] = (dp[i-1][j] * j + dp[i-1][j-1]) % MOD
# return dp[n][k]
dp = [0] * (k + 1)
dp[0] = 1
for i in range(1, n + 1):
ndp = [0] * (k + 1)
if i <= k: ndp[i] = 1
for j in range(1, k+1):
ndp[j] = (dp[j] * j + dp[j-1]) % MOD
dp = ndp
return dp[-1]
1246. Palindrome Removal
- DP
class Solution:
def minimumMoves(self, A: List[int]) -> int:
@cache
def dp(i, j):
if i > j: return 0
res = dp(i, j - 1) + 1
if A[j] == A[j - 1]: res = min(res, dp(i, j - 2) + 1)
for k in range(i, j - 1):
if A[j] != A[k]: continue
res = min(res, dp(i, k - 1) + dp(k + 1, j - 1))
return res
return dp(0, len(A)-1)
40. Combination Sum II
- Backtrack
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
results = []
def backtrack(candidate, total, i):
if total == target:
results.append(candidate.copy())
return
if i == len(candidates): return
for j, num in enumerate(candidates[i:], i):
if j > i and candidates[j] == candidates[j-1]: continue
if total + num > target: continue
candidate.append(num)
total += num
backtrack(candidate, total, j + 1)
total -= num
candidate.pop()
backtrack([], 0, 0)
return results
486. Predict the Winner
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
n = len(nums)
# dp[l][r] is the score for the player at turn
dp = [[0] * n for _ in range(n)] # np.zeros((n, n))
parents = dict()
for l in reversed(range(n)):
for r in range(l, n):
if l == r:
dp[l][r] = nums[l]
parents[(l, r)] = ((l, r), nums[l])
else:
a = nums[l] - dp[l+1][r]
b = nums[r] - dp[l][r-1]
if a > b:
dp[l][r] = a
parents[(l, r)] = ((l+1, r), nums[l])
else:
dp[l][r] = b
parents[(l, r)] = ((l, r-1), nums[r])
if dp[0][-1] >= 0:
state = (0, n-1)
turn = 1
while parents[state][0] != state:
print(f"player {turn % 2} took {parents[state][1]}")
state = parents[state][0]
turn += 1
return dp[0][-1] >= 0
1140. Stone Game II
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
N = len(piles)
for i in range(N - 2, -1, -1): piles[i] += piles[i + 1]
@cache
def dp(i, m):
if i + 2 * m >= N: return piles[i]
return piles[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))
return dp(0, 1)
464. Can I Win
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
seen = {}
def backtrack(choices, remainder):
if choices[-1] >= remainder: return True
seen_key = tuple(choices)
if seen_key in seen: return seen[seen_key]
for index in range(len(choices)):
if not backtrack(choices[:index] + choices[index + 1:], remainder - choices[index]):
seen[seen_key] = True
return True
seen[seen_key] = False
return False
if (maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal: return False
choices = list(range(1, maxChoosableInteger + 1))
return backtrack(choices, desiredTotal)
698. Partition to K Equal Sum Subsets
- Bacjtrack
- Medium
- O(N*2^N)
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
subset_sum, reminder = divmod(sum(nums), k)
if reminder: return False
# optional pre-pruning
for num in nums:
if num > subset_sum: return False
if num == subset_sum: k -= 1
if k == 0 or k == 1: return True
nums = sorted([num for num in nums if num < subset_sum], reverse=True)
return self.solution_backtrack(nums, k, subset_sum)
@staticmethod
def solution_backtrack_v2(nums, k, subset_sum):
def backtrack(state, i, group, accum):
if group == k: return True
if accum > subset_sum: return False
if accum == subset_sum: return backtrack(state, 0, group + 1, 0)
last_used = None
for j, num in enumerate(nums[i:], i):
if state[j]: continue
if num == last_used: continue
last_used = num
state[j] = 1
if backtrack(state, j, group, accum + nums[j]): return True
state[j] = 0
return False
return backtrack([0] * len(nums), 0, 0, 0)
1434. Number of Ways to Wear Different Hats to Each Other
- DP
- Hard
- O(PH*2^P)
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
hats_to_ppl = [[] for _ in range(41)]
for p, p_hats in enumerate(hats):
for hat in p_hats:
hats_to_ppl[hat].append(p)
n = len(hats)
fully_assigned = (1 << n) - 1
@cache
def backtrack(i, ppl_state):
if ppl_state == fully_assigned: return 1
if i == 41: return 0
val = backtrack(i+1, ppl_state)
for ppl in hats_to_ppl[i]:
mask = 1 << ppl
if ppl_state & mask: continue
val += backtrack(i+1, ppl_state | mask)
return val % 1_000_000_007
return backtrack(0, 0)
902. Numbers At Most N Given Digit Set
- DP
- Hard
- O(N)
class Solution:
def atMostNGivenDigitSet(self, D: List[str], N: int) -> int:
N = str(N)
n = len(N)
res = sum(len(D) ** i for i in range(1, n))
i = 0
while i < len(N):
res += sum(c < N[i] for c in D) * (len(D) ** (n - i - 1))
if N[i] not in D: break
i += 1
return res + (i == n)
600. Non-negative Integers without Consecutive Ones
- DP
- Hard
- O(N)
class Solution:
def findIntegers(self, n: int) -> int:
dp = [1,2]
for i in range(30):
dp.append(dp[-1] + dp[-2])
total = 0
prev = 0
i = 30
while i >= 0:
if n & (1 << i):
total += dp[i]
if prev:
total -=1
break
prev = 1
else:
prev = 0
i -= 1
return total + 1
1067. Digit Count in Range
- DP
- Hard
- O(logN)
class Solution:
def digitsCount(self, d: int, low: int, high: int) -> int:
def count(N):
if N == 0: return 0
if d == 0 and N <= 10: return 0
res = 0
if N % 10 > d: res += 1
if N // 10 > 0: res += str(N // 10).count(str(d)) * (N % 10)
res += N // 10 if d else N // 10 - 1
res += count(N // 10) * 10
return res
return count(high + 1) - count(low)
333. Largest BST Subtree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def solution_recursive(self, root: TreeNode) -> int:
def dfs(node):
'''
Returns:
largest bst subtree size from this node
largest bst subtree size if including this node
whether the subtree including this node is valid bst
minimal node value in subtree from this node
maximal node value in subtree from this node
'''
if not node: return 0, 0, 1, float('inf'), float('-inf')
v = node.val
l_max_size, l_size, l_valid, l_min, l_max = dfs(node.left)
r_max_size, r_size, r_valid, r_min, r_max = dfs(node.right)
this_size, this_valid = 0, 0
if l_valid and r_valid and l_max < v < r_min:
this_valid = 1
this_size = l_size + r_size + 1
this_max_size = max(l_max_size, r_max_size, this_size)
this_min = min(l_min, node.val)
this_max = max(r_max, node.val)
return this_max_size, this_size, this_valid, this_min, this_max
return dfs(root)[0]
def solution_iterative(self, root):
stack = [root]
base_case = (0, 0, 1, float('inf'), float('-inf'))
annotation = dict()
visited = set()
while stack:
node = stack.pop()
if not node: continue
v = node.val
if node in visited:
l_max_size, l_size, l_valid, l_min, l_max = annotation.get(node.left, base_case)
r_max_size, r_size, r_valid, r_min, r_max = annotation.get(node.right, base_case)
this_size, this_valid = 0, 0
if l_valid and r_valid and l_max < v < r_min:
this_valid = 1
this_size = l_size + r_size + 1
this_max_size = max(l_max_size, r_max_size, this_size)
this_min = min(l_min, node.val)
this_max = max(r_max, node.val)
annotation[node] = (this_max_size, this_size, this_valid, this_min, this_max)
else:
visited.add(node)
stack.extend([node, node.right, node.left])
return annotation.get(root, base_case)[0]
largestBSTSubtree = solution_iterative # solution_recursive
1273. Delete Tree Nodes
class Solution:
def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
childrens = defaultdict(set)
for nd, par in enumerate(parent):
if nd == 0: continue
childrens[par].add(nd)
num_nodes = nodes
subtree_sums = dict()
subtree_sizes = dict()
stack = [(0, 0)]
while stack:
node, post = stack.pop()
if not post:
stack.append((node, 1))
for child in childrens[node]:
stack.append((child, 0))
else:
subtree_sum = value[node]
subtree_size = 1
for child in childrens[node]:
subtree_sum += subtree_sums[child]
subtree_size += subtree_sizes[child]
subtree_sums[node] = subtree_sum
subtree_sizes[node] = subtree_size
if subtree_sum == 0:
num_nodes -= subtree_size
subtree_sizes[node] = 0
return num_nodes
###