Dynamic Programming

理论

动态规划适合解决多阶段决策最优解模型的问题，若一个最优问题的解决过程需要经历多个决策阶段，每个阶段对应一组状态，然后寻找一组决策序列，经过这组决策序列，能够产生最优值。

适合动态规划的问题必须满足 3 个特征：

  • 最优子结构，问题的最优解包含子问题的最优解，可以通过子问题的最优解推导出问题的最优解。或者说后面阶段的状态可以通过前面阶段的状态推导出来。

  • 无后效性：

    • 在推导后面阶段状态时，只关心前面阶段的状态值，不关心这个值是怎么一步步推导得来的。

    • 某阶段的状态一旦确定，就不受之后阶段的决策影响。

  • 重复子问题，不同的决策序列，达到某个相同阶段时，可能会产生重复的状态。

举例分析，一个 n*n 的矩阵，存储正整数，从左上角到右下角移动，只能向右或向下移动，路径上经过的数字之和为路径的长度，求最短路径长度。

  • 总共要走 2*(n-1) 步，每一步都需要做向右或向下的决策，符合多阶段决策最优解模型。

  • 状态定义为 min_dist(i, j)，表示 (0, 0) 到 (1, 1) 的最短路径长度，符合最优子结构：min_dist(i, j) = w[i][j] + min(min_dist(i, j - 1), min_dist(i - 1, j))

  • 根据上面的公式，我们只关心上一步状态的值，符合无后效性。

  • 到达位置 (i, j)，有多条路线，即符合重复子问题。

思路

解决动态规划问题一般有两种思路。

状态转移表法

一般能用动态规划解决的问题都可以用回溯解决。解决问题的步骤：

  1. 回溯算法实现

  2. 定义状态

  3. 画递归树

  4. 找重复子问题

  5. 画状态转移表，状态表一般为二维数组，每个状态有行、列、值三个变量，如果问题比较复杂，状态表也可能是多维的。

  6. 依据递推关系填表，从前往后，依据递推关系，分阶段填充状态表中的每个状态。

  7. 将填表过程翻译成代码

在第 4 步找到重复子问题后，除了使用状态转移表法，还可以使用回溯加备忘录的方式，效率是差不多的。

以上文的最短路径为例，先用回溯实现：

定义状态为 (i, j, dist)，表示到达 (i, j) 的路径长度为 dist，画递归树：

从状态树中可以看出，尽管 (i, j, dist) 不存在重复，但是 (i, j) 有很多重复，我们只需要选出 (i, j) 中 dist 最小的节点，所以存在重复子问题。画状态转移表，并一步一步填充：

翻译成动态规划的代码：

状态转移方程法

  1. 找最优子结构，分析某个问题是如何通过子问题来递归求解

  2. 写状态方程，即递推公式

  3. 将状态方程翻译成代码，一般有两种实现方式，一种是递归加备忘录，一种是递推迭代（其实与状态转移表的实现是一样的，只是思路不一样）。

还是以上文的最短路径为例，状态方程上面已经给出：

然后用递归加备忘录的方式实现：

案例

0-1 背包

见回溯算法一节的 0-1 背包问题，画递归树：

定义状态 (i, cw)，表示在决策第 i 个物品是否放入背包时，当前背包重量为 cw。有很多重复子问题，画状态转移表，states[n][w + 1] 每一行表示第 i 个物品决策完后，当前背包中的重量有哪些值：

翻译成代码：

时间复杂度 O(n*w)，空间复杂度 O(n*w)，空间复杂度可以优化为 O(w)，用一个 w + 1 的一维数据记录状态：

0-1 背包问题升级版

物品有价值，选择某些物品放入背包，在满足背包最大重量限制的条件下，背包中的总价值最大。

同样用回溯可以解决：

递归树如下：

可以看出，(2, 2, 4) 和(2, 2, 3)，我们只需要选择前者，即对于相同的 (i, cw)，只需要保留 cv 最大的那个。states[n][w + 1] 中保存的是当前状态的最大值：​

莱文斯距离

LeetCode 72。

编辑距离：将一个字符串转换为另一个字符串，需要的最少编辑操作（增加、删除、替换）次数。编辑距离越小，说明两个字符串越相似。

莱文斯距离允许增加、删除、替换三种操作，最长公共子串只允许增加、删除两种操作。

用回溯处理莱文斯距离，两个字符串 a、b，编辑 a 以得到 b。当 a[i] 和 b[j] 匹配时，递归匹配 a[i + 1] 和 b[j + 1]；若不匹配，则：

  • 删除 a[i]，递归匹配 a[i + 1] 和 b[j]

  • 在 a[i] 前增加一个字符 b[j]，递归匹配 a[i] 和 b[j + 1]

  • 把 a[i] 替换成 b[j]，递归匹配 a[i + 1] 和 b[j + 1]

定义状态 (i, j, min_edist)，表示处理到 a[i], b[j] 时，已经编辑的最小次数，状态转移方程：

状态表的填充过程：

转换为代码：

最长公共子串

只允许增加和删除，状态 (i, j, max_lcs) 表示 a[0:i], b[0:j] 的最长公共子串，状态转移方程：

PreviousBack TrackingNextNetwork Protocol

Last updated

Was this helpful?