详解动态规划算法

一、动态规划的核心思想

动态规划的核心思想是将复杂问题分解为简单的子问题，并通过存储子问题的解来避免重复计算，从而节省计算时间。动态规划通常适用于满足以下两个条件的问题：

1. 最优子结构（Optimal Substructure）：一个问题的最优解可以由其子问题的最优解构成。
2. 重叠子问题（Overlapping Subproblems）：问题可以分解为许多重复的子问题，而这些子问题的解会被多次利用。

---

二、动态规划的步骤

解决动态规划问题时，通常遵循以下步骤：

1. 定义状态（State）

首先，我们需要定义一个状态，用来描述问题的子结构。在实际操作中我们通常会定义一个数组或表格来存储子问题的结果。要注意状态的定义应该尽量简单，但又能包含足够的信息来从中推导出最终的解。

2. 确定状态转移方程（State Transition Equation）

状态转移方程是解决动态规划问题的关键，它描述了如何从一个子问题的解推导出更大问题的解。状态转移方程通常是递推公式，能够根据已解决的子问题来构造当前问题的解。

3. 确定边界条件（Base Case）

对于最小的子问题（也就是递归的基础情形），需要明确给出其解，这些就是边界条件。在实现时，这些边界条件是动态规划算法的起点，通常是一些初始值。。

4. 填表（Table Filling）或递归计算

• 自底向上：通过循环填充表格（通常是二维数组或一维数组），从最小的子问题开始，逐步计算出最终的解。
• 自顶向下：通过递归调用子问题，并使用备忘录（Memoization）存储已计算的结果，避免重复计算。

---

三、动态规划的两种常见实现方式

1. 自顶向下（备忘录法）

在自顶向下的方法中，我们通过递归来解决问题，每当遇到一个子问题时，首先检查它是否已经被计算过。如果已经计算过，则直接返回存储的结果；如果没有计算过，则进行递归计算，并将结果存储起来，以便以后使用。

# 定义一个计算斐波那契数列的函数，使用记忆化递归优化性能
def fibonacci(n, memo={}):# 如果 n 已经在 memo 字典中，直接返回 memo[n]，避免重复计算if n in memo:return memo[n]# 基本情况：斐波那契数列的前两项分别是 0 和 1if n <= 1:return n# 递归计算第 n 项的值：# 第 n 项等于第 (n-1) 项和第 (n-2) 项的和# 并将结果存储到 memo 字典中，供后续调用时直接使用memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)# 返回计算结果return memo[n]# 调用函数计算斐波那契数列的第 10 项
print(fibonacci(10))  # 输出 55

这个例子使用了递归，且用 memo 字典存储已经计算过的斐波那契数。

2. 自底向上（迭代法）

自底向上的方法通常通过迭代来逐步填充动态规划表格。首先解决最小的子问题，然后逐步解决更大的子问题，直到最后得到原问题的解。

# 定义一个计算斐波那契数列的函数，使用动态规划（DP）实现
def fibonacci(n):# 基本情况：如果 n 小于等于 1，直接返回 n# 因为斐波那契数列的第 0 项是 0，第 1 项是 1if n <= 1:return n# 初始化一个长度为 (n+1) 的列表 dp，用于存储斐波那契数列的每一项# dp[i] 表示斐波那契数列的第 i 项dp = [0] * (n + 1)# 显式设置斐波那契数列的第 1 项为 1dp[1] = 1# 使用循环从第 2 项开始计算到第 n 项# 每一项 dp[i] 等于前两项 dp[i-1] 和 dp[i-2] 的和for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]# 返回斐波那契数列的第 n 项return dp[n]# 调用函数计算斐波那契数列的第 10 项
print(fibonacci(10))  # 输出 55

这里使用一个一维数组 dp 存储每个斐波那契数，从 dp[0] 到 dp[n]，并通过迭代计算出最终的结果。

---

四、动态规划的经典应用

1. 背包问题

问题描述：

• 给定 n 个物品，每个物品有重量和价值。
• 背包的最大容量是 C，要求在不超过容量限制的情况下，使得背包中的物品总价值最大。

动态规划解法：

动态规划的核心思想是使用一个二维数组 dp[i][w] 来表示前 i 个物品放入容量为 w 的背包时的最大价值。

状态转移方程：

1. 如果当前物品的重量大于背包的剩余容量，那么当前物品不能放入背包。此时最大价值等于不放当前物品时的最大价值：

   $dp[i][w]=dp[i-1][w]$

2. 如果当前物品的重量小于等于背包的剩余容量，我们可以选择放入或不放入当前物品：

   • 不放入当前物品，最大价值为 dp[i-1][w]。
   • 放入当前物品时，最大价值为 dp[i-1][w - weight[i-1]] + value[i-1]（即背包容量减去当前物品的重量，然后加上当前物品的价值）。

   所以状态转移方程为：

   $dp[i][w]=\max (dp[i-1][w],dp[i-1][w-weight[i-1]]+value[i-1])$

初始化：

• dp[0][w] = 0：表示没有物品时，不管背包容量如何，最大价值都是0。
• dp[i][0] = 0：表示背包容量为0时，不管有多少物品，最大价值都是0。

时间复杂度：

• 由于 dp 数组的大小是 (n+1) * (C+1)，其中 n 是物品的数量，C 是背包的容量，所以时间复杂度是 O(n * C)。

代码实现：

def knapsack(weights, values, C):"""0-1背包问题的动态规划解法:param weights: 物品的重量列表:param values: 物品的价值列表:param C: 背包的最大容量:return: 背包的最大价值"""n = len(weights)  # 物品的数量# 创建一个二维dp数组，初始化为0dp = [[0] * (C + 1) for _ in range(n + 1)]# dp[i][w] 表示前i个物品在背包容量为w时的最大价值# 动态规划填充dp数组for i in range(1, n + 1):  # 遍历每个物品for w in range(1, C + 1):  # 遍历每个可能的背包容量if weights[i - 1] <= w:# 如果当前物品的重量小于等于当前背包容量# 选择放入当前物品或者不放入当前物品dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])# dp[i - 1][w] 表示不放入当前物品的最大价值# dp[i - 1][w - weights[i - 1]] + values[i - 1] 表示放入当前物品的最大价值else:# 当前物品太重，不能放入背包dp[i][w] = dp[i - 1][w]  # 继承上一个物品的最大价值# 返回背包容量为C时的最大价值return dp[n][C]# 示例测试
weights = [2, 3, 4, 5]  # 物品的重量
values = [3, 4, 5, 6]   # 物品的价值
C = 5                   # 背包的最大容量print(knapsack(weights, values, C))  # 输出 7

代码解释：

1. 初始化 dp 数组：dp[i][w] 表示前 i 个物品放入容量为 w 的背包时的最大价值。dp 数组的大小为 (n+1) * (C+1)，初始化为0。
2. 填充 dp 数组：从 i = 1 到 n，从 w = 1 到 C，对于每一个物品，我们判断是否能将该物品放入当前容量为 w 的背包。如果能放，则选择放与不放之间的最大值。
3. 最终结果：dp[n][C] 即为考虑所有 n 个物品和容量为 C 时背包的最大价值。

解释：

假设有 n = 4 个物品，分别为：

• 物品1：重量 2，价值 3
• 物品2：重量 3，价值 4
• 物品3：重量 4，价值 5
• 物品4：重量 5，价值 6

背包的容量为 C = 5。

动态规划算法通过逐步选择物品，最终得出背包最大价值为 7，即选择物品1（重量 2，价值 3）和物品2（重量 3，价值 4），总重量为 5，总价值为 7。

其他优化：

• 空间优化：可以使用一维数组优化空间，从 dp[i][w] 改为 dp[w]，每次更新时从右往左更新，避免覆盖还未使用的值。

2. 最长公共子序列（LCS）

最长公共子序列（Longest Common Subsequence, LCS）是指在给定的两个字符串中，找到一个既是这两个字符串的子序列，又是它们的最长的一个子序列。子序列的定义是：从原字符串中删除某些字符（可以不删除任何字符）而不改变其他字符的顺序，得到的新字符串就是子序列。

问题描述：

给定两个字符串 X 和 Y，要求找出它们的最长公共子序列的长度。

动态规划解法：

用一个二维数组 dp[i][j] 来表示前 i 个字符和前 j 个字符的最长公共子序列的长度。

1. 状态定义：

• dp[i][j] 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。

2. 状态转移方程：

• 如果 X[i-1] == Y[j-1]：这意味着当前两个字符相同，当前最长公共子序列长度可以通过将 X[i-1] 或 Y[j-1] 加入到之前的最长公共子序列中得到。此时：

  $dp[i][j]=dp[i-1][j-1]+1$

• 如果 X[i-1] != Y[j-1]：当前两个字符不同，意味着我们无法将这两个字符加入到公共子序列中。因此，最大值来自于之前的两种选择（要么不考虑 X[i-1]，要么不考虑 Y[j-1]）：

  $dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$

3. 边界条件：

• dp[0][j] = 0：当字符串 X 长度为 0 时，和任何字符串 Y 的最长公共子序列长度为 0。
• dp[i][0] = 0：当字符串 Y 长度为 0 时，和任何字符串 X 的最长公共子序列长度为 0。

4. 最终结果：

最终的结果，即两个字符串的最长公共子序列的长度，将存储在 dp[len(X)][len(Y)] 中。

动态规划的空间优化：

虽然 dp 数组是二维的，但我们每次计算时仅依赖于前一行的值，因此可以通过滚动数组将空间复杂度从 O(m * n) 降低为 O(n)。

代码实现：

def longestCommonSubsequence(X, Y):"""动态规划求解最长公共子序列（LCS）的长度:param X: 第一个字符串:param Y: 第二个字符串:return: LCS 的长度"""m = len(X)  # 第一个字符串的长度n = len(Y)  # 第二个字符串的长度# 初始化 dp 数组，dp[i][j] 表示 X[0..i-1] 和 Y[0..j-1] 的 LCS 长度dp = [[0] * (n + 1) for _ in range(m + 1)]# 填充 dp 数组for i in range(1, m + 1):  # 遍历第一个字符串的每个字符for j in range(1, n + 1):  # 遍历第二个字符串的每个字符if X[i - 1] == Y[j - 1]:  # 如果当前字符相同# LCS 长度等于去掉这两个字符后的 LCS 长度加1dp[i][j] = dp[i - 1][j - 1] + 1else:  # 如果当前字符不同# LCS 长度等于去掉一个字符后的 LCS 长度的最大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])# 返回 LCS 的长度，即 dp[m][n]return dp[m][n]# 示例测试
X = "ABCBDAB"
Y = "BDCAB"
print(longestCommonSubsequence(X, Y))  # 输出 4

代码解析：

1. 初始化 dp 数组：dp[i][j] 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。初始化时，dp[i][0] 和 dp[0][j] 都为 0。
2. 状态转移：我们通过嵌套的 for 循环遍历所有的 i 和 j，根据 X[i-1] 和 Y[j-1] 是否相等来更新 dp[i][j]。
3. 返回结果：最终的最长公共子序列的长度在 dp[m][n] 位置，即 X 和 Y 完整字符串的最长公共子序列长度。

示例分析：

假设 X = "ABCBDAB" 和 Y = "BDCAB"：

1. 比较 X[0] 和 Y[0]：A 和 B 不同，dp[1][1] = 0。
2. 比较 X[0] 和 Y[1]：A 和 D 不同，dp[1][2] = 0。
3. 比较 X[0] 和 Y[2]：A 和 C 不同，dp[1][3] = 0。
4. 比较 X[0] 和 Y[3]：A 和 A 相同，dp[1][4] = 1。
5. 比较 X[1] 和 Y[0]：B 和 B 相同，dp[2][1] = 1。
6. 比较 X[1] 和 Y[1]：B 和 D 不同，dp[2][2] = 1。
   …

最终的 dp 表格会被填充如下（仅显示关键部分）：

		B	D	C	A	B
A	0	0	0	0	1	1
B	0	1	1	1	1	2
C	0	1	1	1	1	2
B	0	1	2	2	2	3
D	0	1	2	2	2	3
A	0	1	2	2	3	3
B	0	1	2	2	3	4

最终 dp[7][5] = 4，表示字符串 X = "ABCBDAB" 和 Y = "BDCAB" 的最长公共子序列长度为 4，最长公共子序列为 "BCAB"。

时间和空间复杂度：

• 时间复杂度：O(m * n)，其中 m 和 n 分别是两个字符串的长度，因为我们需要遍历整个 dp 数组。
• 空间复杂度：O(m * n)，我们需要一个 m * n 的二维数组来存储中间结果。

如果我们需要空间优化，可以通过滚动数组的技巧将空间复杂度降为 O(min(m, n))。

---

五、动态规划的优化技巧

• 空间优化：当动态规划表格很大时，可以通过优化空间来减少空间复杂度。例如，在计算背包问题时，我们只需要保留上一行的结果，因此可以将二维数组压缩为一维数组。

• 状态压缩：将多维数组压缩成一维数组，尤其是在状态之间仅依赖于前一状态的情况。

---

六、总结

动态规划是解决具有最优子结构和重叠子问题的优化问题的一种强大工具。通过定义合适的状态和状态转移方程，可以将问题的复杂度从指数级降低到多项式级。掌握动态规划的技巧和方法，将能有效地解决很多经典的计算机算法问题，如背包问题、最长公共子序列、编辑距离等。