【经典算法】解锁动态规划：从思想到代码的奇妙之旅

动态规划算法是一种将复杂问题分解为相互关联子问题的高效解法。文章系统介绍了该算法的核心思想、适用条件和实现步骤，包括最优子结构、无后效性等关键概念，并通过斐波那契数列、背包问题等经典案例进行代码演示。此外还探讨了滚动数组、剪枝等优化技巧，以及该算法在路径规划、资源分配、字符串处理等领域的实际应用。最后展望了动态规划在人工智能、大数据等新兴领域的发展前景，为读者掌握这一重要算法提供了系统指导。

大雨淅淅1999

422人浏览 · 2025-09-30 21:42:16

大雨淅淅1999 · 2025-09-30 21:42:16 发布

一、引言

二、动态规划算法的基本思想

2.1 定义与核心概念

2.2 与其他算法的区别（分治法、贪心算法）

一、引言

在计算机科学的广阔领域中，算法犹如闪耀的星辰，照亮了我们解决复杂问题的道路。而动态规划算法，无疑是其中一颗璀璨夺目的明星，它以独特的魅力和强大的能力，在众多领域发挥着关键作用。无论是在数据挖掘中从海量数据里精准提取有价值信息，还是在机器学习里助力模型优化以提升性能，亦或是在人工智能领域为智能决策提供坚实支撑，动态规划算法都展现出了不可替代的价值。

为了让大家更直观地感受动态规划算法的奇妙之处，我们不妨来看一个生活中的例子。想象你是一位准备开启环球之旅的旅行者，手中的旅行资金有限，而你想去的各个城市都有着不同的旅行价值（可以理解为旅行体验、收获等的量化），并且前往每个城市的交通费用也各不相同。你希望在有限的资金下，规划出一条能让旅行价值最大化的路线。这时候，动态规划算法就能大显身手，它能帮助你综合考虑每个城市的价值和到达该城市的成本，通过巧妙的计算，找到最优的旅行方案，让你的旅行既经济又充实。这个例子虽然简单，但却生动地体现了动态规划算法在解决最优决策问题时的强大能力。接下来，就让我们一起深入探索动态规划算法的世界，揭开它神秘的面纱。

二、动态规划算法的基本思想

2.1 定义与核心概念

动态规划算法，简单来说，就是把一个复杂得让人头疼的大问题，巧妙地拆解成一系列相互关联的子问题。就好像把一个巨大的拼图拆分成一个个小的拼图块，通过逐步解决这些小问题，最终成功拼出整个大拼图，从而解决原始的复杂问题。在这个过程中，有两个非常关键的概念，就像是动态规划这座大厦的两根重要支柱，那就是最优子结构和重叠子问题。

先来说说最优子结构。想象一下你要规划一条从城市 A 到城市 Z 的最短路线，中间需要经过多个城市。这条从 A 到 Z 的最短路线，其实是由从 A 到各个中间城市的最短路线以及从这些中间城市到 Z 的最短路线组合而成的。这就是最优子结构的概念，即问题的最优解可以由其子问题的最优解推导得出。在斐波那契数列中，第 n 项的值等于第 n - 1 项和第 n - 2 项的值之和，这就是斐波那契数列的最优子结构。在背包问题里，如果背包的容量为 W，有 n 个物品，每个物品有自己的重量和价值，那么在不超过背包容量的情况下，能装入背包的最大价值，是由考虑放入或不放入每个物品后，剩余容量下能获得的最大价值推导出来的，这也是最优子结构的体现。

再讲讲重叠子问题。还以斐波那契数列为例，在计算斐波那契数列的第 n 项时，需要不断地重复计算前面的项。比如计算 F (5) = F (4) + F (3)，而计算 F (4) 又需要计算 F (3) 和 F (2)，这里 F (3) 就被重复计算了。这种在解决问题过程中，子问题被多次重复计算的情况，就是重叠子问题。动态规划算法利用一个表格或者数组来存储这些已经计算过的子问题的解，当再次遇到相同的子问题时，直接从表格中读取结果，而不需要重新计算，大大提高了计算效率。就好比你在做数学作业时，遇到一些反复出现的计算步骤，你把这些计算结果记录下来，下次再遇到同样的计算，直接用之前记录的结果，而不用再重新算一遍，既节省时间又减少出错的可能性。背包问题中，在计算不同容量下能获得的最大价值时，也会出现很多重叠子问题，动态规划同样通过存储子问题的解来避免重复计算。

2.2 与其他算法的区别（分治法、贪心算法）

动态规划算法与分治法、贪心算法虽然都用于解决复杂问题，但它们之间有着明显的区别，就像三把不同类型的钥匙，各自适用于不同的锁。

先看动态规划与分治法的区别。分治法是将一个大问题分解成多个相互独立的子问题，分别求解这些子问题，然后将子问题的解合并起来得到原问题的解。归并排序就是分治法的典型应用，它将一个无序数组不断地一分为二，分别对左右两个子数组进行排序，最后再将排序好的子数组合并成一个有序数组。而归并排序中，左右子数组的排序过程是相互独立的，不存在重叠子问题。动态规划则是将问题分解成相互关联的重叠子问题，通过求解这些重叠子问题，并利用子问题之间的依赖关系，逐步构建出原问题的解。在斐波那契数列的动态规划解法中，我们利用已经计算出的 F (n - 1) 和 F (n - 2) 的值来计算 F (n)，这体现了子问题之间的紧密关联。

再对比一下动态规划与贪心算法。贪心算法在每一步决策时，都只考虑当前状态下的局部最优选择，而不考虑整体的最优解。比如在找零问题中，如果有 1 元、5 元、10 元的硬币，要找给顾客 17 元，贪心算法会优先选择面值最大的 10 元硬币，然后再选择 5 元硬币，最后选择 2 个 1 元硬币。这种方法在某些情况下可以得到最优解，但并不是在所有情况下都能得到全局最优解。而动态规划则是从全局的角度出发，通过分析所有可能的子问题组合，考虑问题的整体最优解。在背包问题中，贪心算法可能会优先选择价值重量比最高的物品放入背包，但这不一定能使最终放入背包的物品总价值最大。动态规划则会通过状态转移方程，全面考虑每个物品放入或不放入背包对总价值的影响，从而找到真正的全局最优解。

三、动态规划算法的适用条件

并不是所有问题都适合用动态规划算法来解决，就像不是所有的钥匙都能打开同一把锁一样。动态规划算法有其特定的适用条件，主要包括最优子结构性质、无后效性和子问题重叠性质。只有当一个问题满足这些条件时，使用动态规划算法才能发挥其优势，高效地找到问题的最优解。

3.1 最优子结构性质

最优子结构性质是动态规划算法应用的关键，就像是房子的基石，没有它，房子就无法稳固建立。简单来说，最优子结构性质指的是问题的最优解可以由其子问题的最优解推导得出。也就是说，如果一个问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。

以背包问题为例，假设有一个背包，它的容量为 5 千克，有 3 个物品，分别是重量为 2 千克、价值为 3 元的物品 A，重量为 3 千克、价值为 4 元的物品 B，以及重量为 1 千克、价值为 2 元的物品 C。我们的目标是在不超过背包容量的情况下，选择物品放入背包，使得背包中物品的总价值最大。

这个问题可以分解为多个子问题。比如，考虑放入物品 A 后，问题就变成了在剩余容量为 3 千克的背包中，从物品 B 和 C 中选择物品，使得总价值最大；如果不放入物品 A，问题就变成了在容量为 5 千克的背包中，从物品 B 和 C 中选择物品，使得总价值最大。而这两个子问题的最优解，共同决定了原问题的最优解。如果我们已经知道在剩余容量为 3 千克时，选择物品 C 能使总价值最大，价值为 2 元；在容量为 5 千克时，选择物品 B 和 C 能使总价值最大，价值为 6 元。那么通过比较放入物品 A 和不放入物品 A 这两种情况下的总价值（放入 A 时总价值为 3 + 2 = 5 元，不放入 A 时总价值为 6 元），我们就能得出原问题的最优解，即不放入物品 A，放入物品 B 和 C，总价值为 6 元。这就是背包问题的最优子结构性质的体现，原问题的最优解是由子问题的最优解推导出来的。

再看看最长公共子序列问题。假设有两个序列 X = [1, 3, 4, 5, 6, 7, 7, 8] 和 Y = [3, 5, 7, 4, 8, 6, 7, 8, 2]，我们要找出它们的最长公共子序列。这个问题也具有最优子结构性质。我们可以将其分解为多个子问题，比如比较 X 的前 i 个元素和 Y 的前 j 个元素的最长公共子序列。如果 X 的第 i 个元素和 Y 的第 j 个元素相等，那么它们的最长公共子序列长度就是 X 的前 i - 1 个元素和 Y 的前 j - 1 个元素的最长公共子序列长度加 1；如果不相等，那么就是 X 的前 i - 1 个元素和 Y 的前 j 个元素的最长公共子序列长度与 X 的前 i 个元素和 Y 的前 j - 1 个元素的最长公共子序列长度中的较大值。通过逐步解决这些子问题，我们就能找到 X 和 Y 的最长公共子序列。在这里，原问题的最优解（最长公共子序列）是由各个子问题的最优解（不同前缀的最长公共子序列）推导出来的。

3.2 无后效性

无后效性是动态规划算法的另一个重要条件，它就像是一条单行线规则，一旦某个状态确定了，后续的操作就只能基于这个状态进行，而不会影响之前已经确定的状态。具体来说，无后效性是指某阶段的状态一旦确定，就不受这个状态以后决策的影响。也就是说，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。

比如在一个城市交通路线规划问题中，我们要从城市 A 经过若干个中间城市到达城市 Z 。假设我们已经确定了从城市 A 到城市 B 的最短路线，那么在后续寻找从城市 B 到城市 Z 的最短路线时，我们只需要关注城市 B 的当前状态（比如 B 的位置、从 A 到 B 的最短距离等），而不需要考虑之前是如何从城市 A 到达城市 B 的，是经过了哪些具体的街道和路口。因为无论之前是通过怎样的路径到达城市 B 的，一旦到达 B，后续的决策（如何从 B 到 Z）只取决于 B 的当前状态，而不会受到之前到达 B 的路径的影响。这就是无后效性的体现，每个阶段的状态只与当前阶段和之前的阶段有关，与之后的阶段无关。

再比如在一个数字序列问题中，有一个数字序列 [1, 2, 3, 4, 5]，我们要计算从序列的第一个数字开始，到每个数字位置的最大累加和。假设我们已经计算出到数字 3 的最大累加和是 6（即 1 + 2 + 3 = 6）。那么在计算到数字 4 的最大累加和时，我们只需要考虑当前数字 4 以及到数字 3 的最大累加和，即 6 + 4 = 10 。而不需要考虑之前是如何计算出到数字 3 的最大累加和的，是先加 1 再加 2 再加 3，还是有其他的计算顺序。因为一旦到数字 3 的最大累加和确定了，后续计算到数字 4 的最大累加和时，就只依赖于这个确定的值和当前的数字 4，不会受到之前计算过程的影响，这也符合无后效性的概念。

3.3 子问题重叠性质

子问题重叠性质是动态规划算法能够提高效率的关键因素之一，它就像是一个高效的记忆工具，避免我们在解决问题时做大量重复的工作。子问题重叠性质是指在求解问题的过程中，会多次重复地求解相同的子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

以斐波那契数列为例，斐波那契数列的定义是 F (n) = F (n - 1) + F (n - 2)，其中 F (1) = 1，F (2) = 1 。如果我们使用递归方法来计算斐波那契数列的第 n 项，会出现大量的重复计算。比如计算 F (5) 时，需要计算 F (4) 和 F (3)，而计算 F (4) 又需要计算 F (3) 和 F (2)，这里 F (3) 就被重复计算了。随着 n 的增大，重复计算的次数会呈指数级增长，导致计算效率非常低。

而动态规划算法则通过记忆化存储子问题的解来避免这种重复计算。我们可以使用一个数组 dp 来存储已经计算过的斐波那契数，dp [i] 表示第 i 个斐波那契数。在计算 F (n) 时，先检查 dp [n] 是否已经有值，如果有，直接返回 dp [n]；如果没有，再按照斐波那契数列的定义计算 F (n)，并将结果存储到 dp [n] 中。这样，每个子问题只需要计算一次，大大提高了计算效率。例如，当计算 F (5) 时，先检查 dp [5]，发现没有值，然后计算 F (5) = F (4) + F (3) 。计算 F (4) 时，先检查 dp [4]，没有值，再计算 F (4) = F (3) + F (2) 。计算 F (3) 时，先检查 dp [3]，没有值，计算 F (3) = F (2) + F (1) 。此时，F (1) 和 F (2) 已知，计算出 F (3) = 2，并将其存储到 dp [3] 中。接着计算出 F (4) = 3，并存储到 dp [4] 中，最后计算出 F (5) = 5，并存储到 dp [5] 中。下次再计算 F (5) 或者其他依赖 F (5) 的子问题时，直接从 dp 数组中读取 F (5) 的值，避免了重复计算。

四、动态规划算法的实现步骤

4.1 确定问题的状态

在运用动态规划算法解决问题时，准确确定问题的状态是至关重要的第一步，它就像是为一艘即将远航的船只确定坐标，只有找准了方向，后续的航行才能顺利进行。状态表示的选择直接影响到问题的求解难度和效率。一般来说，我们需要根据问题的特点和要求，选择合适的变量或变量组合来描述问题在不同阶段的状态。

以背包问题为例，我们通常用两个变量来表示状态：物品的数量和背包的容量。假设我们有 n 个物品，背包的容量为 W，那么可以定义 dp [i][j] 表示在前 i 个物品中，能够放入容量为 j 的背包中的最大价值。在这里，i 和 j 就是用来描述问题状态的关键变量。通过这种状态表示，我们可以清晰地看到，对于每一个物品和每一种背包容量，都有一个对应的最大价值。比如，当 i = 3，j = 5 时，dp [3][5] 表示在前 3 个物品中，能够放入容量为 5 的背包中的最大价值。这样，整个背包问题就被转化为了对一系列 dp 值的求解，每个 dp 值都代表了一个特定状态下的最优解。

再看最长递增子序列问题。给定一个数字序列，我们要找出其中最长的递增子序列的长度。在这个问题中，我们可以定义 dp [i] 表示以第 i 个数字结尾的最长递增子序列的长度。通过这种状态表示，我们可以从左到右依次计算每个位置的 dp 值。例如，对于数字序列 [1, 3, 2, 4]，当 i = 2 时，dp [2] 表示以数字 3 结尾的最长递增子序列的长度。由于前面有数字 1 小于 3，所以 dp [2] = dp [1] + 1 = 2 。这样，通过逐步计算每个位置的 dp 值，最终我们可以找到整个序列中的最长递增子序列的长度。

4.2 定义状态转移方程

在确定了问题的状态之后，接下来的关键步骤就是定义状态转移方程，它就像是搭建起了一座桥梁，将不同状态之间的关系清晰地展现出来，让我们能够从已知的状态逐步推导出未知的状态。状态转移方程描述了如何从一个状态转移到另一个状态，是动态规划算法的核心。

以斐波那契数列为例，它的状态转移方程我们已经非常熟悉：F (n) = F (n - 1) + F (n - 2) 。这里，F (n) 表示第 n 个斐波那契数，F (n - 1) 和 F (n - 2) 分别表示第 n - 1 个和第 n - 2 个斐波那契数。这个方程的含义是，第 n 个斐波那契数是由它前两个斐波那契数相加得到的。比如，当 n = 5 时，F (5) = F (4) + F (3) 。通过这个状态转移方程，我们可以从最初的两个已知的斐波那契数（F (1) = 1，F (2) = 1）开始，逐步计算出后续所有的斐波那契数。

再来看矩阵连乘问题。假设有 n 个矩阵 A1, A2, ..., An，我们要计算它们的连乘积，不同的计算顺序会导致不同的乘法次数。我们定义 m [i][j] 表示计算矩阵 Ai 到 Aj 连乘的最小乘法次数。那么状态转移方程为：

**\(m[i][j] = \begin{cases} 0 & \text{if } i = j \\ \min_{i \leq k \lt j} \{ m[i][k] + m[k + 1][j] + p_{i - 1} \cdot p_k \cdot p_j \} & \text{if } i \lt j \end{cases}\)

其中，pi - 1, pi, ..., pj 是矩阵的维度。当 i = j 时，只有一个矩阵，不需要乘法，所以 m [i][j] = 0 。当 i < j 时，我们需要选择一个中间矩阵 Ak（i ≤ k < j），将矩阵连乘分成两部分：先计算 Ai 到 Ak 的连乘，再计算 Ak + 1 到 Aj 的连乘，最后将这两部分的结果相乘。这里的 m [i][k] + m [k + 1][j] 表示前面两部分的最小乘法次数，pi - 1 ⋅ pk ⋅ pj 表示将这两部分结果相乘所需的乘法次数。通过遍历所有可能的 k 值，取最小值，就得到了 m [i][j] 的值。例如，对于三个矩阵 A1（2×3），A2（3×4），A3（4×5），计算 A1A2A3 的最小乘法次数。首先，当 i = 1，j = 2 时，m [1][2] = 2×3×4 = 24 ；当 i = 2，j = 3 时，m [2][3] = 3×4×5 = 60 ；当 i = 1，j = 3 时，k 可以取 1 或 2 。若 k = 1，m [1][3] = m [1][1] + m [2][3] + 2×3×5 = 0 + 60 + 30 = 90 ；若 k = 2，m [1][3] = m [1][2] + m [3][3] + 2×4×5 = 24 + 0 + 40 = 64 。所以，m [1][3] = 64，即计算 A1A2A3 的最小乘法次数为 64 。

4.3 设定边界条件和初始值

边界条件和初始值就像是房屋的基石，虽然看似平凡，但却是整个动态规划算法大厦稳定的基础，它们确保了算法在最开始和最基本的情况下能够正确运行。边界条件是指问题在某些特殊情况下的解，而初始值则是算法开始计算时所依赖的起点。

以最长公共子序列问题为例，假设有两个序列 X = [x1, x2, ..., xm] 和 Y = [y1, y2, ..., yn]，我们定义 dp [i][j] 表示 X 的前 i 个元素和 Y 的前 j 个元素的最长公共子序列的长度。那么边界条件为：当 i = 0 或 j = 0 时，dp [i][j] = 0 。这是因为如果其中一个序列为空，那么它们的最长公共子序列的长度必然为 0 。初始值就是这些边界条件下的 dp 值，它们为后续的状态转移计算提供了起始点。在实际计算中，我们从这些初始值开始，根据状态转移方程逐步填充 dp 数组。比如，当 X = [1, 2, 3]，Y = [2, 3, 4] 时，首先初始化 dp [0][0] = 0，dp [0][1] = 0，dp [0][2] = 0，dp [0][3] = 0，dp [1][0] = 0，dp [2][0] = 0，dp [3][0] = 0 。然后，根据状态转移方程，当 i = 1，j = 1 时，x1 = 1，y1 = 2，不相等，所以 dp [1][1] = max (dp [0][1], dp [1][0]) = 0 ；当 i = 1，j = 2 时，x1 = 1，y2 = 3，不相等，dp [1][2] = max (dp [0][2], dp [1][0]) = 0 ；当 i = 2，j = 1 时，x2 = 2，y1 = 2，相等，dp [2][1] = dp [1][0] + 1 = 1 。就这样，通过不断地利用边界条件和初始值，以及状态转移方程，我们最终可以计算出 dp [m][n]，即 X 和 Y 的最长公共子序列的长度。

4.4 选择合适的实现方式（递归、迭代）

在实现动态规划算法时，我们面临着递归和迭代两种主要的实现方式，它们各有优缺点，就像是两条不同方向的道路，通向同一个目的地，但沿途的风景和行进的难易程度却有所不同。我们需要根据具体问题的特点来选择合适的实现方式，以达到最佳的计算效率和性能。

递归实现方式是一种自顶向下的方法，它直接按照状态转移方程的定义进行计算，将大问题分解为小问题，然后递归地求解这些小问题。以斐波那契数列为例，递归实现的代码如下：

def fibonacci_recursive(n):

if n == 0:

return 0

elif n == 1:

return 1

else:

return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

递归实现的优点是代码简洁、直观，与状态转移方程的定义紧密相关，非常符合我们的思维逻辑。然而，它的缺点也很明显，就是会存在大量的重复计算，导致计算效率低下。比如在计算 F (5) 时，会重复计算 F (3) 等子问题，随着 n 的增大，重复计算的次数会呈指数级增长，时间复杂度为 O (2^n) 。

迭代实现方式则是一种自底向上的方法，它从边界条件和初始值开始，按照一定的顺序逐步计算出所有状态的值。还是以斐波那契数列为例，迭代实现的代码如下：

def fibonacci_iterative(n):

if n == 0:

return 0

elif n == 1:

return 1

dp = [0] * (n + 1)

dp[0] = 0

dp[1] = 1

for i in range(2, n + 1):

dp[i] = dp[i - 1] + dp[i - 2]

return dp[n]

迭代实现的优点是通过保存已经计算过的子问题的解，避免了重复计算，大大提高了计算效率，时间复杂度为 O (n) 。同时，由于不需要递归调用栈，空间复杂度也可以得到较好的控制。但是，迭代实现的代码相对复杂一些，需要我们仔细规划计算的顺序和状态的存储方式。

一般来说，当问题规模较小，递归实现的重复计算不会对效率产生太大影响时，或者问题的递归结构非常清晰时，可以选择递归实现。而当问题规模较大，对计算效率要求较高时，迭代实现往往是更好的选择。在实际应用中，我们还可以对迭代实现进行进一步的优化，比如使用滚动数组等技术来减少空间复杂度。

五、动态规划算法的代码实现示例

5.1 斐波那契数列

斐波那契数列是一个经典的数学序列，它的定义为：F (0) = 0，F (1) = 1，F (n) = F (n - 1) + F (n - 2)（n > 1）。下面我们用 Python 语言来实现斐波那契数列的计算，并分析不同实现方式的时间和空间复杂度。

递归实现：

def fibonacci_recursive(n):

if n == 0:

return 0

elif n == 1:

return 1

else:

return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

递归实现的优点是代码简洁，直接体现了斐波那契数列的定义。但是，它的时间复杂度非常高，为 O (2^n) 。这是因为在计算过程中，会有大量的重复计算。例如，计算 F (5) 时，需要计算 F (4) 和 F (3)，而计算 F (4) 又需要计算 F (3) 和 F (2)，这里 F (3) 就被重复计算了。随着 n 的增大，重复计算的次数呈指数级增长。空间复杂度主要取决于递归调用栈的深度，为 O (n) 。

迭代实现：

def fibonacci_iterative(n):

if n == 0:

return 0

elif n == 1:

return 1

a, b = 0, 1

for i in range(2, n + 1):

a, b = b, a + b

return b

迭代实现通过循环来计算斐波那契数列，避免了重复计算，时间复杂度为 O (n) 。它只使用了两个变量 a 和 b 来存储中间结果，空间复杂度为 O (1) ，相比递归实现，大大节省了空间。

带备忘录的递归实现：

memo = {}

def fibonacci_memoized(n):

if n == 0:

return 0

elif n == 1:

return 1

if n in memo:

return memo[n]

else:

memo[n] = fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)

return memo[n]

带备忘录的递归实现是在递归的基础上，使用一个字典 memo 来存储已经计算过的斐波那契数。当再次计算相同的数时，直接从字典中获取，避免了重复计算。时间复杂度为 O (n)，因为每个数最多被计算一次。空间复杂度为 O (n)，主要用于存储备忘录中的数据。

5.2 0 - 1 背包问题

0 - 1 背包问题是一个经典的动态规划问题，其描述为：给定 n 个物品，每个物品有重量 weights [i] 和价值 values [i]，以及一个容量为 capacity 的背包。每个物品只能选择放入或不放入背包，要求在不超过背包容量的情况下，选择物品放入背包，使得背包中物品的总价值最大。

状态定义：

我们定义 dp [i][j] 表示在前 i 个物品中，能够放入容量为 j 的背包中的最大价值。

状态转移方程：

对于第 i 个物品，有两种选择：

不放入背包：此时 dp [i][j] = dp [i - 1][j]，即不选择当前物品，背包的价值与前 i - 1 个物品相同。

放入背包：如果当前背包容量 j 大于等于物品 i 的重量 weights [i - 1]，则可以选择放入物品 i，此时 dp [i][j] = dp [i - 1][j - weights [i - 1]] + values [i - 1]，即选择当前物品，背包的价值为前 i - 1 个物品在容量为 j - weights [i - 1] 时的最大价值加上当前物品的价值。

综合考虑，状态转移方程为：

\(dp[i][j] = \begin{cases} dp[i - 1][j] & \text{if } weights[i - 1] \gt j \\ \max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]) & \text{otherwise} \end{cases}\)

代码实现：

def knapsack(weights, values, capacity):

n = len(weights)

dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):

for j in range(1, capacity + 1):

if weights[i - 1] <= j:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])

else:

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

return dp[n][capacity]

时间复杂度：有两层循环，外层循环遍历物品，内层循环遍历背包容量，时间复杂度为 O (n * capacity) 。

空间复杂度：使用了一个二维数组 dp 来存储状态，空间复杂度为 O (n * capacity) 。

优化方法：

我们可以发现，在计算 dp [i][j] 时，只用到了 dp [i - 1][j] 和 dp [i - 1][j - weights [i - 1]]，即只与上一行的数据有关。因此，可以使用滚动数组来优化空间复杂度，将二维数组优化为一维数组。

def knapsack_optimized(weights, values, capacity):

n = len(weights)

dp = [0 for _ in range(capacity + 1)]

for i in range(1, n + 1):

for j in range(capacity, weights[i - 1] - 1, -1):

dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1])

return dp[capacity]

优化后的空间复杂度为 O (capacity)，因为只使用了一个一维数组来存储状态。

5.3 最长公共子序列

最长公共子序列（Longest Common Subsequence，简称 LCS）问题是指：给定两个序列，找到这两个序列中最长的公共子序列的长度。子序列是指在原序列中，通过删除某些元素（也可以不删除）但不改变元素顺序得到的新序列。

状态转移方程推导：

设两个序列为 text1 和 text2，长度分别为 m 和 n 。定义 dp [i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。

当 text1 [i - 1] == text2 [j - 1] 时，说明当前字符匹配，那么 dp [i][j] = dp [i - 1][j - 1] + 1 。

当 text1 [i - 1] != text2 [j - 1] 时，说明当前字符不匹配，那么 dp [i][j] = max (dp [i - 1][j], dp [i][j - 1])，即取左边或上边的最大值。

代码实现：

def longestCommonSubsequence(text1, text2):

m, n = len(text1), len(text2)

dp = [[0 for _ in range(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]:

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

else:

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

return dp[m][n]

复杂度分析：

时间复杂度：有两层循环，外层循环遍历 text1，内层循环遍历 text2，时间复杂度为 O (m * n) 。

空间复杂度：使用了一个二维数组 dp 来存储状态，空间复杂度为 O (m * n) 。

回溯得到最长公共子序列：

我们不仅可以得到最长公共子序列的长度，还可以通过回溯的方法得到具体的最长公共子序列。

def longestCommonSubsequenceAndTraceback(text1, text2):

m, n = len(text1), len(text2)

dp = [[0 for _ in range(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]:

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

else:

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

# 回溯得到最长公共子序列

lcs = []

i, j = m, n

while i > 0 and j > 0:

if text1[i - 1] == text2[j - 1]:

lcs.append(text1[i - 1])

i -= 1

j -= 1

elif dp[i - 1][j] > dp[i][j - 1]:

i -= 1

else:

j -= 1

lcs.reverse()

return dp[m][n], ''.join(lcs)

在回溯过程中，从 dp 数组的右下角开始，如果当前字符匹配，则将该字符加入到最长公共子序列中，并向左上方移动；如果不匹配，则向值较大的方向移动。最后将得到的最长公共子序列反转，得到正确的顺序。

六、动态规划算法的优化技巧

6.1 空间优化（滚动数组等）

在动态规划算法中，空间复杂度是一个需要重点关注的问题。当问题规模较大时，过高的空间复杂度可能导致内存不足，影响算法的正常运行。滚动数组是一种常用的优化空间复杂度的技巧，它在很多动态规划问题中都能发挥重要作用，特别是在 0 - 1 背包问题中。

在 0 - 1 背包问题的常规解法中，我们定义dp[i][j]表示在前i个物品中，能够放入容量为j的背包中的最大价值，使用的是一个二维数组来存储状态，空间复杂度为O(n * capacity)。然而，通过分析状态转移方程：

\(dp[i][j] = \begin{cases} dp[i - 1][j] & \text{if } weights[i - 1] \gt j \\ \max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]) & \text{otherwise} \end{cases}\)

我们可以发现，在计算dp[i][j]时，只用到了dp[i - 1][j]和dp[i - 1][j - weights[i - 1]]，也就是只与上一行的数据有关。这就意味着我们可以使用滚动数组来优化空间复杂度，将二维数组优化为一维数组。

具体实现方法是，我们只使用一个一维数组dp[j]来存储状态。在遍历物品时，对于每个物品i，从背包容量capacity开始，逆向遍历到weights[i - 1]。这样做的原因是，如果正向遍历，在更新dp[j]时，dp[j - weights[i - 1]]可能已经被更新为当前物品i的状态，导致一个物品被重复放入背包，而逆向遍历可以避免这个问题。状态转移方程变为：

\(dp[j] = \max(dp[j], dp[j - weights[i - 1]] + values[i - 1])\)

下面是使用滚动数组优化后的 0 - 1 背包问题的 Python 代码实现：

def knapsack_optimized(weights, values, capacity):

n = len(weights)

dp = [0 for _ in range(capacity + 1)]

for i in range(1, n + 1):

for j in range(capacity, weights[i - 1] - 1, -1):

dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1])

return dp[capacity]

优化前，空间复杂度为O(n * capacity)，使用滚动数组优化后，空间复杂度降为O(capacity)。这在背包容量capacity相对较小，而物品数量n较大时，能显著减少内存的使用。滚动数组的原理就是利用了动态规划中状态转移只依赖于部分之前状态的特性，通过复用数组空间，达到优化空间复杂度的目的。

6.2 时间优化（剪枝策略等）

除了空间优化，时间优化也是动态规划算法优化的重要方面。剪枝策略是一种常用的时间优化技术，它的核心思想是在动态规划求解过程中，通过判断某些子问题的解是否已经可以确定，或者某些分支是否不可能产生最优解，从而提前终止对这些子问题或分支的计算，减少不必要的计算量。

以 0 - 1 背包问题为例，假设我们已经找到了一个当前最优解，其价值为current_max_value。在后续的计算中，如果我们计算到某个状态dp[i][j]时，发现即使将剩余的所有物品都放入背包，所能达到的最大价值也小于current_max_value，那么就可以直接跳过对这个状态及其后续相关状态的计算，因为这个分支不可能产生更优的解。

再比如在解决旅行商问题（TSP）时，我们可以使用动态规划来求解。在计算过程中，当我们尝试扩展某个城市节点时，如果当前路径的长度已经超过了目前找到的最优路径长度，那么就可以直接剪枝，不再继续扩展这个节点及其后续的分支，因为这个分支不可能产生更优的路径。

下面是一个简单的示例代码，展示了在 0 - 1 背包问题中如何应用剪枝策略：

def knapsack_with_pruning(weights, values, capacity):

n = len(weights)

dp = [0 for _ in range(capacity + 1)]

current_max_value = 0

for i in range(1, n + 1):

for j in range(capacity, weights[i - 1] - 1, -1):

new_value = dp[j - weights[i - 1]] + values[i - 1]

dp[j] = max(dp[j], new_value)

# 剪枝操作

remaining_weight = capacity - j

remaining_max_value = 0

for k in range(i + 1, n + 1):

if weights[k - 1] <= remaining_weight:

remaining_max_value = max(remaining_max_value, dp[j - weights[k - 1]] + values[k - 1])

if dp[j] + remaining_max_value <= current_max_value:

break

current_max_value = max(current_max_value, dp[j])

return dp[capacity]

在这个代码中，我们在每次更新dp[j]后，计算剩余物品在剩余容量下的最大价值remaining_max_value。如果当前状态dp[j]加上remaining_max_value都小于当前最优解current_max_value，则直接跳出内层循环，不再继续计算该物品在其他容量下的情况。通过这种剪枝策略，可以有效地减少计算量，提高算法的运行效率。

七、动态规划算法的应用场景

7.1 路径规划问题（如最短路径问题）

在路径规划问题中，动态规划算法有着广泛且重要的应用，其中 Floyd - Warshall 算法是解决所有顶点对之间最短路径问题的经典动态规划算法。该算法适用于带权有向图或无向图，并且能够处理边权重为负数的情况，只要图中不存在负权回路即可正常工作。

算法原理

Floyd - Warshall 算法的核心思想基于动态规划，通过不断尝试引入新的中间节点来更新最短路径。设图中有 n 个顶点，定义D(k, i, j)为只允许经过编号不大于 k 的中间结点时，从 i 到达 j 的最小花费。状态转移方程为：

\( D(k,i,j)=\min(D(k - 1,i,j),D(k - 1,i,k)+D(k - 1,k,j)) \)

其中0≤k < n；当k = 0时，初始化条件为如果存在直接相连的边(i,j)，则设D(0,i,j)等于对应的边权wij；否则设置成无穷大∞ 。这个过程意味着每次增加一个新的可能作为中介点使用的顶点 k 之后，重新评估当前已知的最佳路径长度，直到遍历完所有的可能性为止。

状态定义

在 Floyd - Warshall 算法中，我们定义一个二维数组dist[i][j]来表示从顶点 i 到顶点 j 的最短路径长度。初始时，dist[i][j]等于顶点 i 到顶点 j 的直接距离（如果两节点之间有边相连），或者设为无穷大（如果两节点之间没有直接相连的边）。同时，我们可以定义一个二维数组path[i][j]来记录从顶点 i 到顶点 j 的最短路径中 j 的前一个顶点，以便在找到最短路径长度后，能够回溯出具体的最短路径。

转移方程

对于每一个中间节点 k，我们遍历所有的顶点对(i, j)，如果从顶点 i 经过节点 k 再到节点 j 的路径长度小于当前记录的从顶点 i 到节点 j 的最短路径长度，即dist[i][k] + dist[k][j] < dist[i][j]，则更新dist[i][j]为dist[i][k] + dist[k][j]，同时更新path[i][j] = k 。转移方程如下：

\( \text{if } dist[i][k] + dist[k][j] \lt dist[i][j]: \\ \qquad dist[i][j] = dist[i][k] + dist[k][j] \\ \qquad path[i][j] = k \)

代码实现

以下是使用 Python 实现 Floyd - Warshall 算法的代码：

def floyd_warshall(graph):

n = len(graph)

# 初始化距离矩阵

dist = [[float('inf') for _ in range(n)] for _ in range(n)]

# 初始化路径矩阵

path = [[-1 for _ in range(n)] for _ in range(n)]

# 初始化对角线上的距离为0

for i in range(n):

dist[i][i] = 0

path[i][i] = i

# 根据图的邻接矩阵初始化距离矩阵和路径矩阵

for i in range(n):

for j in range(n):

if graph[i][j] != 0:

dist[i][j] = graph[i][j]

path[i][j] = j

# Floyd-Warshall算法核心部分

for k in range(n):

for i in range(n):

for j in range(n):

if dist[i][k] != float('inf') and dist[k][j] != float('inf') and dist[i][k] + dist[k][j] < dist[i][j]:

dist[i][j] = dist[i][k] + dist[k][j]

path[i][j] = path[i][k]

return dist, path

# 示例图的邻接矩阵表示，0表示自身到自身，float('inf')表示不可达

graph = [

[0, 5, float('inf'), 10],

[float('inf'), 0, 3, float('inf')],

[float('inf'), float('inf'), 0, 1],

[float('inf'), float('inf'), float('inf'), 0]

]

dist, path = floyd_warshall(graph)

print("最短路径矩阵:")

for row in dist:

print(row)

print("路径矩阵:")

for row in path:

print(row)

通过上述代码，我们可以得到图中任意两个顶点之间的最短路径长度以及具体的最短路径。例如，从顶点 0 到顶点 2 的最短路径长度可以通过dist[0][2]获取，具体的最短路径可以通过path矩阵回溯得到。

7.2 资源分配问题

在实际生活和工作中，资源分配问题无处不在，比如在项目开发中，我们需要将有限的人力、物力、财力等资源合理地分配到各个项目任务中，以实现项目的最大收益或最小成本。动态规划算法为这类资源分配问题提供了有效的解决方案。

假设我们有一个公司，要开展 N 个项目，目前拥有 M 个单位的资源。每个项目 i 需要消耗一定数量的资源xi，并能产生一定的收益yi 。我们的目标是合理分配这 M 个单位的资源，使得总收益最大化。

问题建模

将这个问题建模为动态规划问题，我们需要确定问题的状态、状态转移方程、初始条件和计算顺序。

状态定义

设dp[i][j]表示前 i 个项目分配 j 个单位资源时所能获得的最大收益。这个状态定义涵盖了项目数量和资源数量两个关键因素，能够全面地描述问题在不同阶段的情况。

求解过程

初始化：dp[0][j] = 0，表示没有项目时，无论分配多少资源，收益都为 0；dp[i][0] = 0，表示没有资源时，无论有多少项目，收益也为 0 。

状态转移：对于每个项目 i 和资源数量 j，我们有两种选择：

不分配资源给项目 i，此时dp[i][j] = dp[i - 1][j]，即收益与前 i - 1 个项目分配 j 个单位资源时相同。

分配资源给项目 i，如果j >= xi（即当前剩余资源足够分配给项目 i），则dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - xi] + yi) 。这里dp[i - 1][j - xi] + yi表示分配资源给项目 i 后，前 i - 1 个项目在剩余j - xi个单位资源下的最大收益加上项目 i 的收益，通过取最大值来确定最优选择。

计算顺序：从小到大依次计算 i 和 j，即先考虑项目数量从 1 到 N，再考虑资源数量从 1 到 M 。通过这样的顺序计算，我们可以逐步构建出整个问题的最优解。

下面是使用 Python 实现上述资源分配问题的代码：

def max_profit(N, M, projects):

dp = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(1, N + 1):

xi, yi = projects[i - 1]

for j in range(M + 1):

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

if j >= xi:

dp[i][j] = max(dp[i][j], dp[i - 1][j - xi] + yi)

return dp[N][M]

# 示例

N = 3

M = 5

projects = [(1, 2), (2, 3), (3, 5)]

print(max_profit(N, M, projects)) # 输出7

在这个例子中，项目的资源需求和收益分别为(1,2), (2, 3), (3, 5)，总资源为 5 。通过动态规划算法，我们计算出最大收益为 7 。这意味着在给定的资源和项目条件下，按照动态规划确定的资源分配方案，可以实现项目收益的最大化。

7.3 字符串处理问题（如编辑距离问题）

在字符串处理领域，编辑距离问题是一个经典的问题，它在文本校对、拼写检查、生物信息学等多个方面都有着广泛的应用。编辑距离，也称为莱文斯坦距离（Levenshtein Distance），是指将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数。这些单字符编辑操作包括插入一个字符、删除一个字符和替换一个字符。

例如，将字符串 “kitten” 转换为 “sitting”，可以通过以下操作：

将 “k” 替换为 “s”，这是一次替换操作。

删除 “e”，这是一次删除操作。

插入 “i”，这是一次插入操作。

总共需要 3 次操作，所以 “kitten” 和 “sitting” 的编辑距离为 3 。

动态规划求解方法

状态定义

设dp[i][j]为将字符串 A 的前 i 个字符转换为字符串 B 的前 j 个字符所需的最少操作次数。

转移方程推导

初始化：

当i = 0时，即 A 为空字符串，要将空字符串转换为 B 的前 j 个字符，需要插入 j 个字符，所以dp[0][j] = j 。

当j = 0时，即 B 为空字符串，要将 A 的前 i 个字符转换为空字符串，需要删除 i 个字符，所以dp[i][0] = i 。

当i = 0且j = 0时，两个空字符串之间的编辑距离为 0，即dp[0][0] = 0 。

状态转移：

当A[i - 1] == B[j - 1]时，当前字符相同，无需额外操作，问题可以递归为子问题，即dp[i][j] = dp[i - 1][j - 1] 。

当A[i - 1] != B[j - 1]时，需要选择以下三种操作之一，并选择代价最小的路径：

删除操作：删除A[i - 1]，对应转化为子问题dp[i - 1][j] + 1 。这是因为删除一个字符后，只需将 A 的前i - 1个字符转换为 B 的前 j 个字符，操作次数增加 1 。

插入操作：在 A 中插入一个字符，使其匹配B[j - 1]，对应子问题dp[i][j - 1] + 1 。插入一个字符后，需要将 A 的前 i 个字符转换为 B 的前j - 1个字符，操作次数增加 1 。

替换操作：将A[i - 1]替换为B[j - 1]，对应子问题dp[i - 1][j - 1] + 1 。替换一个字符后，需要将 A 的前i - 1个字符转换为 B 的前j - 1个字符，操作次数增加 1 。

综合上述情况，状态转移方程为：

\( dp[i][j] = \begin{cases} dp[i - 1][j - 1], & \text{if } A[i - 1] = B[j - 1] \\ 1 + \min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]), & \text{if } A[i - 1] \neq B[j - 1] \end{cases} \)

代码实现

以下是使用 Python 实现编辑距离问题的代码：

def min_edit_distance(A, B):

m, n = len(A), len(B)

# 初始化dp表

dp = [[0] * (n + 1) for _ in range(m + 1)]

# 填充第一行和第一列

for i in range(m + 1):

dp[i][0] = i

for j in range(n + 1):

dp[0][j] = j

# 填充dp表

for i in range(1, m + 1):

for j in range(1, n + 1):

if A[i - 1] == B[j - 1]:

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

else:

dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

return dp[m][n]

# 示例

A = "horse"

B = "ros"

result = min_edit_distance(A, B)

print(f"将字符串 '{A}' 转换为 '{B}' 的最小编辑距离是: {result}")

通过上述代码，我们可以计算出任意两个字符串之间的编辑距离。在实际应用中，编辑距离常被用于衡量字符串之间的相似性。编辑距离越小，说明两个字符串越相似。例如，在拼写检查中，如果用户输入的单词与字典中的某个单词编辑距离较小，那么可以提示用户可能想要输入的是该字典单词。在生物信息学中，编辑距离可以用于比较 DNA 序列或蛋白质序列的相似性，帮助研究人员分析物种之间的进化关系等。

八、总结与展望

动态规划算法作为一种强大的算法思想，其基本思想是将复杂问题分解为相互关联的子问题，通过求解子问题并利用子问题的解来构建原问题的最优解。它的核心在于最优子结构和重叠子问题，这使得我们能够高效地解决许多传统方法难以处理的复杂问题。

在实现动态规划算法时，关键步骤包括准确确定问题的状态，清晰定义状态转移方程，合理设定边界条件和初始值，以及根据问题特点选择合适的实现方式（递归或迭代）。同时，为了进一步提升算法的性能，我们还可以运用空间优化（如滚动数组）和时间优化（如剪枝策略）等技巧。

动态规划算法的应用领域极为广泛，在路径规划问题中，像 Floyd - Warshall 算法能够高效地找到所有顶点对之间的最短路径；在资源分配问题上，它可以帮助我们合理分配有限资源，实现项目收益的最大化；在字符串处理问题里，例如编辑距离问题，动态规划能够准确衡量字符串之间的相似性。

随着科技的飞速发展，动态规划算法在新兴领域也展现出了巨大的潜力。在人工智能和机器学习领域，动态规划可用于优化模型训练过程，提升模型的性能和效率。在大数据分析中，它能够处理复杂的数据关系，挖掘数据中的潜在价值。未来，动态规划算法有望在更多领域发挥重要作用，为解决各种复杂问题提供更加有效的解决方案。希望读者通过本文的学习，能够深入理解动态规划算法的精髓，并将其灵活应用到实际问题的解决中。

北京朝阳AI社区

更多推荐

【74页PPT】智慧方案桥工地顶层设计方案（附下载方式）

北京朝阳AI社区

【人工智能通识专栏】第三十一讲：文献分析与综述

北京朝阳AI社区

大模型+BI：AI应用架构师如何增强企业数字化管理平台的数据分析能力？

销售总监拿着BI报表拍桌子：“这个月销量下降15%，到底是客户流失还是竞品抢单？运营经理盯着库存图表叹气：“明明仓库堆了1000台空调，为什么还在进货？财务总监翻着成本报表摇头：“广告费花了50万，怎么没带来半点增长？传统BI的核心是“数据呈现”——把分散的销售、库存、财务数据整理成报表、图表，但它解决不了“为什么”和“怎么办”的问题。就像你有一本详细的家庭账本，能看到“这个月花了3000块菜钱”