DP
Two List
Template
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(m):
for j in range(n):
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
if text1[i] == text2[j]:
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
What I have done
583. Delete Operation for Two Stringsconvert one string to another string, delete, insert, convert
1143. Longest Common Subsequence
Range DP --> Palindromic Substring / Sequence
Template
palindromic substring
for i in range(n):
dp[i][i] = 1
if i > 0:
dp[i][i-1] = 1
for length in range(2, n + 1):
for i in range(0, n-length+1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = 2 + dp[i+1][j-1]
palindromic sequence
for length in range(2, n + 1):
for i in range(0, n-length+1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = 2 + dp[i+1][j-1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1]) # 最长连续子串就没有这里
What I have done
5. Longest Palindromic Substring
🌟115. Distinct Subsequences
131. Palindrome Partitioning
516. Longest Palindromic Subsequence
647. Palindromic Substrings
718. Maximum Length of Repeated Subarray
1035. Uncrossed Lines
1312. Minimum Insertion Steps to Make a String
Tree DP
Template
def dfs(node):
nonlocal ans
if not node:
return 2
left_state = dfs(node.left)
right_state = dfs(node.right)
if left_state == 0 or right_state == 0:
ans += 1
return 1
if left_state == 1 or right_state == 1:
return 2
return 0
What I have done
337. House Robber III
968. Binary Tree Cameras
Alice and Bob
Template
1-D
for i in range(n-1, -1, -1):
for m in range(1, n+1):
if i + 2 * m >= n:
dp[i][m] = suffix[i]
else:
for x in range(1, 2 * m + 1):
bob_score = dp[i+x][max(x, m)]
alice_score = suffix[i] - bob_score
dp[i][m] = max(dp[i][m], alice_score)
What I have done
486. Predict the Winnerboth players are playing optimally??
1140. Stone Game II
Knapsack Problem
0-1 Knapsack Problem
Template
recursive formula
dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j] dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
for i in range(len(nums)):
for j in range(target, nums[i] - 1, -1): # Iterate from target down to nums[i]
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
What I have done
416. Partition Equal Subset Sum
494. Target Sum方案数就是+=
1049. Last Stone Weight II转化为将一堆stone放进最大容量为sum/2的背包,求放进去的石头的最大重量MaxWeight,最终答案即为sum-2*MaxWeight
474. Ones and Zeroesweight可以是二维
Unbounded Knapsack Problem
Template
for i in range(len(weight)):
for j in range(weight[i], bagWeight + 1):
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
组合数
for i in range(len(coins)):
for j in range(coins[i], amount+1):
dp[j] += dp[j-coins[i]]
排列数
for j in range(1, target+1):
for i in range(len(nums)):
if j < nums[i]:
continue
dp[j] += dp[j-nums[i]]
What I have done
279. Perfect Squares
377. Combination Sum IV排列
518. Coin Change II组合
Other
What I have done
96. Unique Binary Search Trees
343. Integer Break
House Robber
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
198. House Robber 213. House Robber II
Best Time to Buy and Sell Stock
Template
What I have done
121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III
188. Best Time to Buy and Sell Stock IV
309. Best Time to Buy and Sell Stock with Cooldown
714. Best Time to Buy and Sell Stock with Transaction
Math
Template
nums = [1]
i_2 = 0
i_3 = 0
i_5 = 0
while len(nums) < n:
nxt_2 = nums[i_2] * 2
nxt_3 = nums[i_3] * 3
nxt_5 = nums[i_5] * 5
nxt = min(nxt_2, nxt_3, nxt_5)
nums.append(nxt)
if nxt == nxt_2:
i_2 += 1
if nxt == nxt_3:
i_3 += 1
if nxt == nxt_5:
i_5 += 1
return nums[n-1]
What I have done
264. Ugly Number II
313. Super Ugly Number
🌟1201. Ugly Number III容斥+二分