动态规划

1
2
3
4
5
6
7
8
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...:
dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...)

1
2
3
4
5
def fib(N):
if N == 1 or N == 2:
return 1
return fib(N - 1) + fib(N - 2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def fib(self, N: int) -> int:
if N < 1: return 0
memo = [0] * (N + 1)
# 备忘录全部初始化为 0
def helper(memo, n):
if n == 1 or n == 2:
# base case
return 1
if memo[n] != 0:
# 已经计算过
return memo[n]
memo[n] = helper(memo, n - 1) + helper(memo, n - 2)
return memo[n]
return helper(memo, N)
# 进行带备忘录的递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def fib(self, N: int) -> int:
if N < 1:
return 0
if N == 1 or N == 2:
return 1
dp = [0] * (N + 1)
dp[1] = dp[2] = 1
# base case
for i in range(3, N + 1):
dp[i] = dp[i - 1] + dp[i - 2]
# 状态转移方程
return dp[N]

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def fib(self, N: int) -> int:
if N == 0:
return 0
if N == 1:
return 1
prev, curr = 0, 1
for i in range(2, N + 1):
prev, curr = curr, prev + curr
return curr

1
2
3
4
5
6
7
8
9
10
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.
1 阶 + 1 阶 + 1 阶
2.
1 阶 + 2 阶
3.
2 阶 + 1 阶

1
2
3
4
5
6
7
8
class Solution:
def climbStairs(self, n: int) -> int:
if n < 2: return n
pre, cur = 1, 2
for i in range(2, n):
pre, cur = cur, pre + cur
return cur

1
2
3
4
5
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

1
2
3
4
5
6
7
class Solution:
def rob(self, nums: List[int]) -> int:
pre, cur = 0, 0
for i in range(len(nums)):
pre, cur = cur, max(cur, pre + nums[i])
return cur

1
2
3
4
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def rob(self, nums: List[int]) -> int:
length = len(nums)
if not nums or length == 0:
return 0
if length == 1:
return nums[0]
def rob(nums, first, last):
pre, cur = 0, 0
for i in range(first, last + 1):
pre, cur = cur, max(cur, pre + nums[i])
return cur
return max(rob(nums, 0, length - 2), rob(nums, 1, length - 1)) # 抢劫第一个就不能抢劫最后一个

1
2
3
4
5
6
7
8
9
class Solution:
def rob(self, nums: [int]) -> int:
def my_rob(nums):
cur, pre = 0, 0
for num in nums:
cur, pre = max(pre + num, cur), cur
return cur
return max(my_rob(nums[:-1]), my_rob(nums[1:])) if len(nums) != 1 else nums[0]

1
2
3
4
5
6
7
输入:
[[1,3,1],
[1,5,1],
[4,2,1]]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
dp = [[grid[0][0]] * len(grid[0]) for _ in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid[0])):
if i == 0 and j == 0:
continue
elif i == 0:
dp[i][j] = dp[i][j - 1] + grid[i][j]
elif j == 0:
dp[i][j] = dp[i - 1][j] + grid[i][j]
else:
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
return dp[-1][-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
dp = [0] * len(grid[0])
for i in range(len(grid)):
for j in range(len(grid[0])):
if j == 0:
dp[j] = dp[j]
elif i == 0:
dp[j] = dp[j - 1]
else:
dp[j] = min(dp[j - 1], dp[j])
dp[j] += grid[i][j]
return dp[-1]

1
2
3
4
5
6
7
8
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for _ in range(m)]
for i in range(m):
# 第一行从最左边到当前位置，只有一条路径
dp[i][0] = 1
for j in range(n):
# 第一列从最上边到当前位置，只有一条路径
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]

1
2
3
4
5
6
7
8
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] = dp[j] + dp[j - 1]
return dp[-1]

1
2
3
4
5
6
7
8
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。

1
2
3
4
5
6
7
8
class NumArray:
def __init__(self, nums: List[int]):
self.sum_ = [0] * (len(nums) + 1)
for i in range(1, len(nums) + 1):
self.sum_[i] = self.sum_[i - 1] + nums[i - 1]
def sumRange(self, i: int, j: int) -> int:
return self.sum_[j + 1] - self.sum_[i]

1
2
3
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[2] = 1
[0, 1, 2]
dp[3] = dp[2] + 1 = 2
[0, 1, 2, 3], // [0, 1, 2] 之后加一个 3
[1, 2, 3]
// 新的递增子区间
dp[4] = dp[3] + 1 = 3
[0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4
[1, 2, 3, 4],
// [1, 2, 3] 之后加一个 4
[2, 3, 4]
// 新的递增子区间

1
2
3
4
5
6
7
8
9
10
class Solution:
def numberOfArithmeticSlices(self, A: List[int]) -> int:
if not A: return 0
length = len(A)
dp = [0] * length
for i in range(2, length):
if A[i] - A[i - 1] == A[i - 1] - A[i - 2]:
dp[i] = dp[i - 1] + 1
return sum(dp)

1
2
3
4
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
# 拆分数字 i
for j in range(1, i):
# 拆分为 i、i-j
# 将 j * dp[i - j]、j * (i - j) 中的最大值与 dp[i] 比较，得到最大值
dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j)))
return dp[-1]

1
2
3
4
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

1
2
3
4
5
6
7
8
9
class Solution:
def numSquares(self, n: int) -> int:
dp = [i for i in range(n + 1)]
for i in range(2, n + 1):
for j in range(1, int(i ** (0.5)) + 1):
dp[i] = min(dp[i], dp[i - j * j] + 1)
print(dp)
return dp[-1]

1
2
3
4
5
'A' -> 1
'B' -> 2
...
'Z' -> 26

1
2
3
4
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def numDecodings(self, s: str) -> int:
len_ = len(s)
if len_ == 0 or s[0] == '0':
return 0
dp = [0] * len_
dp[0] = 1
for i in range(1, len_):
if s[i] != '0':
dp[i] = dp[i - 1]
num = 10 * (ord(s[i - 1]) - ord('0')) + (ord(s[i]) - ord('0'))
if 10 <= num <= 26:
if i == 1:
dp[i] += 1
else:
dp[i] += dp[i - 2]
return dp[- 1]

1
2
3
4
5
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明: 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
dp = [1] * len(nums)
# 初始化为 1，即自身为最长递增子序列
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

1
2
3
4
5
6
7
8
以输入序列 [0, 8, 4, 12, 2] 为例：
第一步插入 0，d = [0]；
第二步插入 8，d = [0, 8]；
第三步插入 4，d = [0, 4]；
第四步插入 12，d = [0, 4, 12]；
第五步插入 2，d = [0, 2, 12]。 此插入更改了元素的相对顺序，不符合子序列，但长度并未增加，答案仍然正确，只是如果后面仍然有大于 2 但小于 12 的多个整数，便能增加最长子序列的长度，忽略这一步则长度不会增加，导致错误。
最终得到最大递增子序列长度为 33。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
d = []
# 长度为 i 的最长上升子序列的末尾元素的最小值
for n in nums:
if not d or n > d[-1]:
d.append(n)
else:
# d 为递增数组，在 d 中使用二分查找
l, r = 0, len(d) - 1
loc = r
while l <= r:
mid = (l + r) // 2
if d[mid] >= n:
loc = mid
r = mid - 1
else:
l = mid + 1
d[loc] = n
return len(d)

1
2
3
4
输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
if len(pairs) == 0: return 0
pairs.sort()
dp = [1] * len(pairs)
for i in range(len(pairs)):
for j in range(i):
if pairs[i][0] > pairs[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

1
2
3
4
5
6
7
8
9
10
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
cur, res = float('-inf'), 0
pairs.sort(key = lambda n: n[1])
for x, y in pairs:
if cur < x:
cur = y
res += 1
return res

1
2
3
4
5
6
7
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
n = len(nums)
if n == 0 or n == 1:
return n
up, down = 1, 1
for i in range(1, n):
if nums[i] > nums[i - 1]:
up = down + 1
elif nums[i] < nums[i - 1]:
down = up + 1
return max(up, down)

1
2
3
4
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestclass Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
def dp(i, j):
# 空串的 base case
if i == -1 or j == -1:
return 0
if text1[i] == text2[j]:
# 这边找到一个 lcs 元素，继续往前找
return dp(i - 1, j - 1) + 1
else:
# 谁能让 lcs 最长，就听谁的
return max(dp(i - 1, j), dp(i, j - 1))
# i 和 j 初始化为最后一个索引
return dp(len(text1) - 1, len(text2) - 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# 构建 DP table 和 base case
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 进行状态转移
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
# 找到一个 lcs 中的字符
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def knapsack(self, W, N, wt, val):
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] # base case，已初始化
for i in range(1, N + 1):
for w in range(1, W + 1):
# 处理 w - wt[i-1] 可能小于 0 导致数组索引越界的问题
if w - wt[i - 1] < 0:
# 选择不装入背包
dp[i][w] = dp[i - 1][w]
else:
# 装入或不装入背包，择优
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])
return dp[N][W]

1
2
3
4
5
6
7
8
9
class Solution:
def knapsack(self, W, N, wt, val):
dp = [0] * (W + 1)
for i in range(1, N + 1):
for j in range(W, 0, -1):
if j >= wt[i - 1]:
dp[j] = max(dp[j], dp[j - wt[i - 1]] + val[i - 1])
return dp[-1]

1
2
3
4
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def canPartition(self, nums: List[int]) -> bool:
sum_ = sum(nums)
if sum_ % 2 == 1:
# 和为奇数时，不可能划分成两个和相等的集合
return False
n = len(nums)
sum_ = sum_ // 2
dp = [[True] + [False] * sum_ for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, sum_
+ 1):
if j - nums[i - 1] < 0:
# 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j]
else:
# 装入或不装入背包
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
return dp[n][sum_]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def canPartition(self, nums: List[int]) -> bool:
ele_sum = sum(nums)
if ele_sum % 2 == 1:
# 和为奇数时，不可能划分成两个和相等的集合
return False
n = len(nums)
ele_sum = ele_sum // 2
dp = [False for _ in range(ele_sum + 1)]
dp[0] = True
for i in range(1, n):
for j in range(ele_sum, 0, -1):
if j - nums[i] >= 0:
dp[j] = dp[j] or dp[j - nums[i]]
return dp[ele_sum]

1
2
3
4
5
6
7
8
9
10
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。

1
2
3
4
5

sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
sum_ = sum(nums)
if sum_ < S or (sum_ + S) % 2 == 1:
return 0
p = (sum_ + S) // 2
dp = [1] + [0] * w
for num in nums:
for i in range(p, num - 1, -1):
dp[i] = dp[i] + dp[i - num]
return dp[p]

1
2
3
4
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
if len(strs) == 0:
return 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
# ones = s.count('1')
# zeros = s.count('0')
ones, zeros = 0, 0
for c in s:
if c == '0':
zeros += 1
else:
ones += 1
# 遍历可容纳的背包，每个字符为一个新背包
for i in range(m, zeros - 1, -1):
for j in range(n, ones - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
return dp[m][n]

1
2
3
4
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

1
2
coins = [1, 2, 5], amount = 11, 输出：3

1
2
3
4
5
6
7
8
9
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

1
2
3
4
5
6
7
8
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = len(coins)
dp = [[0] * (amount + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1
for i in range(1, n + 1):
for j in range(1, amount + 1):
if j - coins[i - 1] >= 0:
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
else:
dp[i][j] = dp[i - 1][j]
return dp[n][amount]

1
2
3
4
5
6
7
8
9
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]

1
2
3
4
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

1
2
["lee", "tc", "cod"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
# 背包的迭代
for word in wordDict:
# 物品的迭代
len_ = len(word)
if len_ <= i and word == s[i - len_: i]:
dp[i] = dp[i] or dp[i - len_]
return dp[n]

1
2
3
4
5
6
7
8
9
10
11
12
13
nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
maximum = [0] * (target + 1)
maximum[0] = 1
nums.sort()
for i in range(1, target + 1):
for j in range(len(nums)):
if nums[j] <= i:
maximum[i] += maximum[i - nums[j]]
return maximum[target]