动态规划

0. 动态规划

• 动态规划 (Dynamic Programming) 问题的一般形式就是求最值，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
• 求解动态规划的核心问题是穷举，因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。

动态规划的思考模式：

1. 动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
2. 动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
3. 虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出**正确的「状态转移方程」**才能正确地穷举。

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

按上面的套路走，最后的结果就可以套这个框架：

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

1. 斐波那契数列

1. 暴力递归:

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

递归算法的时间复杂度 = 子问题个数 x 解决一个子问题需要的时间。

1. 计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
2. 计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。

所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别。

暴力递归中存在大量的重复计算，也就是重叠子问题，所以时间复杂度高。

2. 带备忘录的递归方法:

将先计算的子问题的答案记录在备忘录中，后计算的子问题先去备忘录中查一查，如果答案已经存在，则直接将答案拿出来使用。

一般使用数组充当备忘录，也可以使用哈希表。

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)
# 进行带备忘录的递归

时间复杂度：子问题个数为 O(n)，解决一个子问题的时间为 O(1)，所以算法的时间复杂度为 O(n)。

• 自顶向下：从上向下延伸，从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案。即以上两种方法。
• 自底向上：直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

3. dp 数组的迭代解法：

把这个「备忘录」独立出来成为一张表，叫做 DP table ，在这张表上完成「自底向上」的推算：

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]

4. dp 数组的状态压缩解法：

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

如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，上述例子就相当于把DP table 的大小从 n 缩小到 2。一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从 O(n^2) 压缩到 O(n)。

1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.
1 阶 + 1 阶 + 1 阶
2.
1 阶 + 2 阶
3.
2 阶 + 1 阶

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

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

2. 强盗抢劫

抢劫一排住户，但是不能抢邻近的住户，求最大抢劫金额。

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

定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。

由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以强到第 i + 1 个住户的最大金额为 max(抢到第 i 个住户的最大值，抢到第 i - 1 个住户的最大值 + nums[i+1])。

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

3. 强盗在环形街区抢劫

抢劫一环形住户，但是不能抢邻近的住户，求最大抢劫金额。

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

由于住户为环形的，所以抢劫了第一个就不能抢劫最后一个，因此将抢劫分为两部分：

1. 从第一个到倒数第二个
2. 从第二个到倒数第一个

返回其中的最大值。

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)) # 抢劫第一个就不能抢劫最后一个

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]

以上为两种不同的写法。

2. 矩阵路径

1. 矩阵的最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

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

1. 二维动态规划： dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]，从左上向右下前进。

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]

2. 一维动态规划：

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]

2. 矩阵的总路径数

统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动。

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

1. 二维动态规划：除第一行、第一列外，从左上角到当前位置的路径数为 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

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]

2. 一维动态规划：

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]

3. 数组区间

1. 数组区间和

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

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

求区间 i ~ j 的和，可以转换为 sum[j + 1] - sum[i]，其中 sum[i] 为 0 ~ i - 1 的和。

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]

2. 数组中等差递增自区间的个数

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

数组 A 包含 N 个数，且索引从 0 开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0 <= P < Q < N 。

如果满足以下条件，则称子数组 (P, Q) 为等差数组：

元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

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

算法：

• dp[i] ：以A[i] 为结尾的等差递增子区间的个数。

当 A[i] - A[i-1] == A[i-1] - A[i-2]，那么 [A[i-2], A[i-1], A[i]] 构成一个等差递增子区间。而且在以 A[i-1] 为结尾的递增子区间的后面再加上一个 A[i]，一样可以构成新的递增子区间。

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]
// 新的递增子区间

综上，在 A[i] - A[i-1] == A[i-1] - A[i-2] 时，dp[i] = dp[i-1] + 1。

因为递增子区间不一定以最后一个元素为结尾，可以是任意一个元素结尾，因此需要返回 dp 数组累加的结果。

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)

4. 分割整数

1. 分割整数的最大乘积

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

说明: 你可以假设 n 不小于 2 且不大于 58。

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

• dp[i]：数字 i 拆分为至少两个正整数之和的最大乘积 。
• 外层循环 i：从 2 开始遍历，到 n 停止，因为最小只有 2 可以拆分成两个正整数之和。
• 内层循环 j：从 1 开始遍历，到 i 之前停止，表示数字 i 可以拆分成 i = j + (i - j)，但 j * (i - j) 不一定是最大乘积，因为 i - j 不一定大于 dp[i - j]，即 i - j 不一定大于 i - j 的整数拆分的最大乘积。每一次外层循环，都有 i - 1 中拆分方法，其中的最大值即为所求。

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]

2. 按平方数来分割整数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

dp[i]：i 最少可以由几个平方数构成

1. 初始化 dp = [0, 2, 3,...,n]，长度为 n + 1 ，最多次数就是全由 1 构成
2. 遍历 dp ， i 的遍历区间为 [2, n + 1]；内层循环遍历所有平方数小于 i 的数 j，遍历区间 [1, int(i ** 0.5) + 1]，无需全部遍历；保存所有可能情况中的最小值，dp[i] = min(dp[i], dp[i - j * j] + 1)，
3. 返回 dp[-1]

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]

3. 分割整数构成字母字符串

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

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

dp[i]：以 s[i] 结尾的前缀子串有多少种解码方法。

状态方程分类讨论：

1. s[i] != '0' 时，dp[i] = dp[i - 1]，因为如果一个字符为 0，则不能单独编码为任何字符，需要和前一个字符组合进行编码，
2. 10 <= s[i - 1, i] <= 26 时，dp[i] += dp[i - 2]

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]

5. 最长递增子序列

子序列问题相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，一旦涉及到子序列和最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)。

1. 最长递增子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

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

1、动态规划:

按照动态规划定义状态的套路，我们有两种常见的定义状态的方式：

1. dp[i] : 以 i 结尾（一定包括 i）所能形成的最长上升子序列长度, 答案是 max(dp)
2. dp[i] : 以 i 结尾（可能包括 i）所能形成的最长上升子序列长度，答案是 dp[-1] （-1 表示最后一个元素）

• dp[i]：以第 i 个数字结尾的最长上升子序列的长度，其中 nums[i] 必须被选取。
• 状态转移方程：dp[i] = max(dp[i], dp[j] + 1)，其中 0 <= j < i 且 nums[j] < nums[i]，即在 dp[0, i - 1] 中最长的上升子序列后面再加一个 nums[i]。
• 整个数组的最长上升子序列即所有 dp[i] 中的最大值。

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)

以上解法的时间复杂度为 O(N2)，可以使用二分查找将时间复杂度降低为 O(NlogN)。

2、贪心+二分查找：

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

维护一个数组 d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1] = nums[0]。

依次遍历数组 nums 中的元素

• 如果 nums[i] > d[len]，则直接将其加入到数组 d 的末尾，并更新 len += 1，
• 否则在 d 中使用二分查找，找到第一个比 nums[i] 小的数 d[k]，并更新 d[k + 1] = nums[i]。

以输入序列 [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。

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)

2. 一组整数对能够构成的最长链

对于 (a, b) 和 (c, d) ，如果 b < c，则它们可以构成一条链。

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

1、动态规划：

• dp[i]：以 pairs[i] 结尾的最长子链。
• 当 j < i 且 pair[i][0] > pairs[j][1] 时，dp[i] = max(dp[i], dp[j] + 1)。

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)

2、贪心算法：

在所有可作为下一个数对的集合中选择第二个数最小的数对添加到数对链，按照数对第二个数的升序序列遍历所有数对，如果当前数对可以加入链，则加入。

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

3. 最长摆动子序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如，[1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

输入: [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. 如果 nums[i] > nums[i-1] ，意味着这里在摆动上升，前一个数字肯定处于下降的位置。所以 up = down + 1 ，down 保持不变。
2. 如果 nums[i] < nums[i-1] ，意味着这里在摆动下降，前一个数字肯定处于上升的位置。所以 down = up + 1 ， up 保持不变。
3. 如果 nums[i]==nums[i−1] ，意味着这个元素不会改变任何东西因为它没有摆动。所以 down 与 up 都保持不变。

最后，我们可以将 up 和 down 中的较大值作为问题的答案。

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)

6. 最长公共子序列 (LCS)

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

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

动态规划思路：

**子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。**所以可以说只要涉及子序列问题，十有八九都需要动态规划来解决，往这方面考虑就对了。

第一步，构造 dp 数组：

dp[i][j] ：对于 s1[1: i+1] 和 s2[1: j+1]，它们的最长公共子序列长度是 dp[i][j]。

第二步，定义 base case：

让索引为 0 的行和列表示空串，dp[0][..] 和 dp[..][0] 都应该初始化为 0，这就是 base case。

例如 dp[0][3]=0 的含义是：对于字符串 "" 和 "bab"，其最长公共子序列的长度为 0。因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0。

第三步，找状态转移方程：

状态转移说简单些就是做选择，对于本题就是两种选择，要么在 lcs 中，要么不在。如果某个字符应该在 lcs 中，那么这个字符肯定同时存在于 s1 和 s2 中，因为 lcs 是最长公共子序列嘛。

用两个指针 i 和 j 从后往前遍历 s1 和 s2，如果 s1[i] == s2[j]，那么这个字符一定在 lcs 中；否则的话，s1[i] 和 s2[j] 这两个字符至少有一个不在 lcs 中，需要丢弃一个。递归解法如下：

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)

动态规划解法：

对于两个子序列 S1 和 S2

• 当 S1i == S2j 时，那么就能在 S1 的前 i - 1 个字符与 S2 的前 j - 1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即 dp[i][j] = dp[i - 1] + 1。
• 当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i - 1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j - 1 个字符最长公共子序列，取它们的最大者，即 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

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]

与最长递增子序列相比，最长公共子序列有以下不同点：

• 针对的是两个序列，求它们的最长公共子序列。
• 在最长递增子序列中，dp[i] 表示以 Si 为结尾的最长递增子序列长度，子序列必须包含 Si ；在最长公共子序列中，dp[i][j] 表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度，不一定包含 S1i 和 S2j。
• 在求最终解时，最长公共子序列中 dp[N][M] 就是最终解，而最长递增子序列中 dp[N] 不是最终解，因为以 SN 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。

7. 0-1 背包

描述：给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

动态规划标准套路：

1、明确「状态」和「选择」：

• 状态：「背包的容量」和「可选择的物品」
• 选择：「装进背包」或者「不装进背包」

2、明确 dp 数组的定义：

• dp[i][w]：只选择前 i 个物品，且背包的容量为 w 时，可以装的最大价值为 dp[i][w]
• base case：dp[0][..] = dp[..][0] = 0，即没有物品或者背包没有空间的时候，能装的最大价值就是 0
• dp[N][W]：最终答案

3、根据「选择」，思考状态转移的逻辑：

• 如果你没有把这第 i 个物品装入背包，dp[i][w] = dp[i - 1][w]。
• 如果你把这第 i 个物品装入了背包， dp[i][w] = dp[i - 1][w - wt[i - 1]] + val[i - 1]。
• 状态转移方程：dp[i][W] = max(dp[i - 1][W], dp[i - 1][w - wt[i - 1]] + val[i - 1])。

由于 i 是从 1 开始的，所以 val 和 wt 的索引是 i-1 时表示第 i 个物品的价值和重量。

代码：

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]

空间优化：

观察状态转移方程可以知道，前 i 件物品的状态仅与前 i - 1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。即：dp[j] = max(dp[j], dp[j - wt[i - 1]] + val[i - 1])。

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]

需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。

1. 划分数组为和相等的两部分

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意：每个数组中的元素不会超过 100，数组的大小不会超过 200

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

那么对于这个问题，我们可以先对集合求和，得出 sum，把问题转化为背包问题：

给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i] 。现在让你装物品，是否存在一种装法，能够恰好将背包装满？

动态规划思考步骤：

1、明确「状态」和「选择」：

• 状态：「背包的容量」和「可选择的物品」
• 选择：「装进背包」或者「不装进背包」

2、明确 dp 数组的定义：

• dp[i][j] = x：对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。
• base case：dp[..][0] = true 和 dp[0][..] = false，因为背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没办法装满背包。
• dp[N][sum // 2]：最终答案。

3、根据「选择」，思考状态转移的逻辑：

• 如果不把 nums[i] 算入子集，或者说不把这第 i 个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i - 1][j]，继承之前的结果。
• 如果把 nums[i] 算入子集，或者说把这第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i - 1][j - nums[i - 1]]。
• 状态转移方程：dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]。

由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]

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_]

进行状态压缩：

注意到 dp[i][j] 都是通过上一行 dp[i-1][..] 转移过来的，可以进行状态压缩，将二维 dp 数组压缩为一维，节约空间复杂度：

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]

需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。

2. 改变一组数的正负号使得它们的和为一给定数

给定一个非负整数数组，a1, a2, ..., an 和一个目标数 S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 - 中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

输入：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。

该问题可以转换为子集和 (即上题) 问题，从而使用 0-1 背包的方法来求解。

可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：

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

因此只要找到一个子集 P，令其和等于 (target + sum(nums)) // 2，就证明存在解。

• 开辟一个长度为 P+1 的数组，命名为 dp
• dp 的第 x 项，代表组合成数字 x 有多少方法。比如说，dp[0] = 1，代表组合成 0 只有 1 中方法，即什么也不取。比如说 dp[5] = 3 ，代表使总和加到 5 总共有三种方法。
• 所以最后返回的就是 dp[P]，代表组合成 P 的方法有多少种。

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]

3. 01字符构成最多的字符串

假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

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

这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。

• dp[i][j]：已经放了多少个字符串，其中 i 表示可用 0 的个数， j 表示可用的 1 的个数。
• 选择：①不放，则查看旧背包放的字符串数；②放，则 1（当前01串）+ 变小的 旧背包放的字符串数。
• 状态转移方程：dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)。

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]

4. 找零钱的最少硬币数

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

因为硬币可以重复使用，因此这是一个完全背包问题。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历即可。

• dp[i]：组成金额 i 所需最少的硬币数量
• 转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)，当枚举到硬币金额为 coin 时，需要从硬币金额 i - coin 所需的硬币数 dp[i - coin] 过渡而来，再算上枚举的这枚硬币数量 1 的贡献。

例：假设

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

可以看到问题的答案是通过子问题的最优解得到的。

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

5. 找零钱的硬币数组合

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

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

我们可以把这个问题转化为背包问题的描述形式：

有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

• dp[i][j]：若只使用前 i 个物品，当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包。即若只使用 coins 中的前 i 个硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。
• base case : dp[0][..] = 0， dp[..][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。
• dp[N][amount]：最终答案

选择：

1. 如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i] 这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] = dp[i - 1][j]。
2. 如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i] 这个面值的硬币，那么 dp[i][j] = dp[i][j - coins[i - 1]]。
3. 我们想求的 dp[i][j] 是「共有多少种凑法」，所以 dp[i][j] 的值应该是以上两种选择的结果之和。

首先由于 i 是从 1 开始的，所以 coins 的索引是 i-1 时表示第 i 个硬币的面值。

dp[i][j-coins[i-1]]：如果你决定使用这个面值的硬币，那么就应该关注如何凑出金额 j - coins[i-1]。比如说，你想用面值为 2 的硬币凑出金额 5，那么如果你知道了凑出金额 3 的方法，再加上一枚面额为 2 的硬币，就可以凑出 5 了。

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]

状态压缩：

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]

6. 字符串按单词列表分割

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。

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

dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。

该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中，例如下面的 dict 就不够组成字符串 “leetcode”：

["lee", "tc", "cod"]

求解顺序的完全背包问题时，对物品的迭代应该放在最里层，对背包的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。

• dp[i]：表示 s 的前 i 位是否可以用 wordDict 中的单词表示。

• 初始化 dp[0] = True，空字符可以被表示。

• 遍历字符串的所有子串，遍历开始索引 i，遍历区间 [0, n]：
  遍历 wordDict 中的元素：
  若 len(word) <= i 且 word == s[i - len(word): i] 中：
  dp[i] = True。
  解释：dp[i] = True 说明 s 的前 i 位可以用 wordDict 表示，则 s[i - len(word): i] 出现在 wordDict 中，说明 s 的前 j 位可以表示。
  

• 返回 dp[n]

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]

7. 组合总和

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

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。

涉及顺序的完全背包。

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]

最后

以上就是感动苗条为你收集整理的动态规划的全部内容，希望文章能够帮你解决动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。