## Leetcode DP study plan list II

1. Day 1 Basics of Dynamic Programming
2. Day 2 One Dimensional Dynamic Programming
3. Day 3 One Dimensional Dynamic Programming
4. Day 4 One Dimensional Dynamic Programming
5. Day 5 One Dimensional Dynamic Programming
6. Day 6 One Dimensional Dynamic Programming
7. Day 7 Dynamic Programming on String
8. Day 8 Dynamic Programming on String
9. Day 9 Dynamic Programming on String
10. Day 10 Dynamic Programming on String
11. Day 11 Dynamic Programming on String
12. Day 12 Dynamic Programming on String
13. Day 13 Min/Max Path Sum
14. Day 14 Classic Dynamic Programming Problems
15. Day 15 Memoization
16. Day 16 Unique Paths
17. Out of Boundary Paths
18. Unique Binary Search Trees
19. Day 19 Coin Change / Combination Sum
20. Day 20 Coin Change / Combination Sum
21. Day 21 Partition Equal Subset Sum

## Leetcode DP study plan list III

1. Day 1 Classic Dynamic Programming Problems
2. Day 2 One Dimensional Dynamic Programming
3. Day 3 One Dimensional Dynamic Programming
4. Day 4 One Dimensional Dynamic Programming
5. Day 5 Dynamic Programming on String
6. Day 6 Dynamic Programming on String
7. Day 7 Dynamic Programming on String
8. Day 8 Dynamic Programming on String
9. Day 9 Dynamic Programming on String
10. Day 10 Min/Max Path Sum
11. Day 11 Memoization
12. Day 12 Dynamic Programming on Counting
13. Day 13 Dynamic Programming on Counting
14. Day 14 Dynamic Programming on Counting
15. Day 15 Merge Interval
16. Day 16 Coin Change / Combination Sum
17. Day 17 Backpack questions
18. Day 18 Dynamic Programming on Game Theory
19. Day 19 Dynamic Programming on Game Theory
20. Day 20 Bit Manipulation
21. Day 21 Dynamic Programming on Numbers
22. Day 22 Dynamic Programming on Tree
23. 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, obviously dp[-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 tells us whether we can reach the end from location 0.
def jump(nums):
n = len(nums)
dp =  * 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


Thought process:

• The above procedure is not efficient, as we would need to check a range of values at each step. The dp table stores only binary information.
• We can put more info in the dp table 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 between dp[i - 1] and i + nums[i].
• We pad the dp table with one 1 at the left, since we always can get to the first position.
def jump(nums):
dp =  +  * 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 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


Thought process:

• Same rational as with the Jump Game problem, we can have $$O(n)$$ solution.
def jump(nums):
dp =  * 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 <= s: dp[nums] = 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 = 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 = [ * (n + 1) for i in range(minProfit + 1)]
dp = 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 =  + [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 =  +  * 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] + p > dp[-1]:
dp.append([e, dp[prev] + p])
return dp[-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)
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] + v > ndp[-1]:
ndp.append([e, dp[i] + v])
dp, ndp = ndp, [[0, 0]]
return dp[-1][-1]


### 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
#
# 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] = max(dp[i], dp[i-1] - price)
dp[i] = max(dp[i], price + dp[i])
return dp[k]


## 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 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 = [ * (len(s) + 1) for _ in range(len(t) + 1)]
dp =  * (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):  return 2 + f(i+1, j-1), s[i]
return max(f(i+1, j), f(i, j-1))
return f(0, n -1)

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]:
dp[i][j] = [dp[i+1][j-1] + 2, s[i]]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
i += 1; j += 1
return dp[n-1]

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 = [ * 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]

def solution_1d_bottm_up(self, s: str) -> int:
# compress to use two alternating rows
n = len(s)
prev =  * n
for r in range(n):
curr =  * 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

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 = grid

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)
dp = defaultdict(lambda: -1)
dp[(0,0,ncol-1)] = grid + grid[ncol-1]
max_val = grid + grid[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 = [ * n for _ in range(n)]
probs[row][column] = 1

while k:
n_probs = [ * 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)
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


### 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 =  * (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 = [ * (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 =  * (k + 1)
dp = 1
for i in range(1, n + 1):
ndp =  * (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 = [ * 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[-1] >= 0:
state = (0, n-1)
turn = 1
while parents[state] != state:
print(f"player {turn % 2} took {parents[state]}")
state = parents[state]
turn += 1

return dp[-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( * 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]:
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



### 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)

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:
stack.extend([node, node.right, node.left])
return annotation.get(root, base_case)

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

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


###