动态规划

动态规划（Dynamic Programming, DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。

参考：

https://oi-wiki.org/dp/ （主参考）
https://www.hello-algo.com/chapter_dynamic_programming/ (主参考)
https://github.com/azl397985856/leetcode （参考问题）

1 动态规划的问题特性

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

1.1 最优子结构

具有最优子结构也可能是适合用贪心的方法求解。

注意要确保我们考察了最优解中用到的所有子问题。

证明问题最优解的第一个组成部分是做出一个选择；
对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面：

原问题的最优解中涉及多少个子问题；
确定最优解使用哪些子问题时，需要考察多少种选择。

子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

Note

实际上，子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同。

分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。

动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。

回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。

1.2 无后效性

无后效性是动态规划能够有效解决问题的重要特性之一，其定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。

以爬楼梯问题为例，给定状态 $i$ ，它会发展出状态 $i + 1$ 和状态 $i + 2$ ，分别对应跳 $1$ 步和跳 $2$ 步。在做出这两种选择时，我们无须考虑状态 $i$ 之前的状态，它们对状态 $i$ 的未来没有影响。

然而，如果我们给爬楼梯问题添加一个约束，情况就不一样了。

带约束爬楼梯

给定一个共有 $n$ 阶的楼梯，你每步可以上 $1$ 阶或者 $2$ 阶，但不能连续两轮跳 $1$ 阶，请问有多少种方案可以爬到楼顶？

如下图所示，爬上第 $3$ 阶仅剩 $2$ 种可行方案，其中连续三次跳 $1$ 阶的方案不满足约束条件，因此被舍弃。

在该问题中，如果上一轮是跳 $1$ 阶上来的，那么下一轮就必须跳 $2$ 阶。这意味着，下一步选择不能由当前状态（当前所在楼梯阶数）独立决定，还和前一个状态（上一轮所在楼梯阶数）有关。

不难发现，此问题已不满足无后效性，状态转移方程 $d p [i] = d p [i - 1] + d p [i - 2]$ 也失效了，因为 $d p [i - 1]$ 代表本轮跳 $1$ 阶，但其中包含了许多“上一轮是跳 $1$ 阶上来的”方案，而为了满足约束，我们就不能将 $d p [i - 1]$ 直接计入 $d p [i]$ 中。

为此，我们需要扩展状态定义：状态 $[i, j]$ 表示处在第 $i$ 阶并且上一轮跳了 $j$ 阶，其中 $j \in {1, 2}$ 。此状态定义有效地区分了上一轮跳了 $1$ 阶还是 $2$ 阶，我们可以据此判断当前状态是从何而来的。

当上一轮跳了 $1$ 阶时，上上一轮只能选择跳 $2$ 阶，即 $d p [i, 1]$ 只能从 $d p [i - 1, 2]$ 转移过来。
当上一轮跳了 $2$ 阶时，上上一轮可选择跳 $1$ 阶或跳 $2$ 阶，即 $d p [i, 2]$ 可以从 $d p [i - 2, 1]$ 或 $d p [i - 2, 2]$ 转移过来。

如下图所示，在该定义下， $d p [i, j]$ 表示状态 $[i, j]$ 对应的方案数。此时状态转移方程为：

{d p [i, 1] = d p [i - 1, 2] d p [i, 2] = d p [i - 2, 1] + d p [i - 2, 2]

最终，返回 $d p [n, 1] + d p [n, 2]$ 即可，两者之和代表爬到第 $n$ 阶的方案总数：

/* 带约束爬楼梯：动态规划 */
int climbingStairsConstraintDP(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    // 初始化 dp 表，用于存储子问题的解
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    // 初始状态：预设最小子问题的解
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[2][1] = 0;
    dp[2][2] = 1;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
    }
    return dp[n][1] + dp[n][2];
}

在上面的案例中，由于仅需多考虑前面一个状态，因此我们仍然可以通过扩展状态定义，使得问题重新满足无后效性。然而，某些问题具有非常严重的“有后效性”。

爬楼梯与障碍生成

给定一个共有 $n$ 阶的楼梯，你每步可以上 $1$ 阶或者 $2$ 阶。规定当爬到第 $i$ 阶时，系统自动会在第 $2 i$ 阶上放上障碍物，之后所有轮都不允许跳到第 $2 i$ 阶上。例如，前两轮分别跳到了第 $2$ 、 $3$ 阶上，则之后就不能跳到第 $4$ 、 $6$ 阶上。请问有多少种方案可以爬到楼顶？

在这个问题中，下次跳跃依赖过去所有的状态，因为每一次跳跃都会在更高的阶梯上设置障碍，并影响未来的跳跃。对于这类问题，动态规划往往难以解决。

实际上，许多复杂的组合优化问题（例如旅行商问题）不满足无后效性。对于这类问题，我们通常会选择使用其他方法，例如启发式搜索、遗传算法、强化学习等，从而在有限时间内得到可用的局部最优解。

1.3 子问题重叠

如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

2 动态规划解题思路

上两节介绍了动态规划问题的主要特征，接下来我们一起探究两个更加实用的问题。

如何判断一个问题是不是动态规划问题？
求解动态规划问题该从何处入手，完整步骤是什么？

2.1 问题判断

总的来说，如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解。然而，我们很难从问题描述中直接提取出这些特性。因此我们通常会放宽条件，先观察问题是否适合使用回溯（穷举）解决。

适合用回溯解决的问题通常满足“决策树模型”，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。

换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。

在此基础上，动态规划问题还有一些判断的“加分项”。

问题包含最大（小）或最多（少）等最优化描述。
问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。

相应地，也存在一些“减分项”。

问题的目标是找出所有可能的解决方案，而不是找出最优解。
问题描述中有明显的排列组合的特征，需要返回具体的多个方案。

如果一个问题满足决策树模型，并具有较为明显的“加分项”，我们就可以假设它是一个动态规划问题，并在求解过程中验证它。

2.2 问题求解步骤

动态规划的解题流程会因问题的性质和难度而有所不同，但通常遵循以下步骤：描述决策，定义状态，建立 $d p$ 表，推导状态转移方程，确定边界条件等。

from https://oi-wiki.org/dp/basic/#基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为状态）；

寻找每一个状态的可能决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程 ）。

按顺序求解每一个阶段的问题。

如果用图论的思想理解，我们建立一个有向无环图，每个状态对应图上一个节点，决策对应节点间的连边。这样问题就转变为了一个在 DAG 上寻找最长（短）路的问题（参见： DAG 上的 DP ）。

为了更形象地展示解题步骤，我们使用一个经典问题“最小路径和”来举例。

Question

给定一个 $n \times m$ 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和。

下图展示了一个例子，给定网格的最小路径和为 $13$ 。

第一步：思考每轮的决策，定义状态，从而得到 $d p$ 表

本题的每一轮的决策就是从当前格子向下或向右走一步。设当前格子的行列索引为 $[i, j]$ ，则向下或向右走一步后，索引变为 $[i + 1, j]$ 或 $[i, j + 1]$ 。因此，状态应包含行索引和列索引两个变量，记为 $[i, j]$ 。

状态 $[i, j]$ 对应的子问题为：从起始点 $[0, 0]$ 走到 $[i, j]$ 的最小路径和，解记为 $d p [i, j]$ 。

至此，我们就得到了下图所示的二维 $d p$ 矩阵，其尺寸与输入网格 $g r i d$ 相同。

第二步：找出最优子结构，进而推导出状态转移方程

对于状态 $[i, j]$ ，它只能从上边格子 $[i - 1, j]$ 和左边格子 $[i, j - 1]$ 转移而来。因此最优子结构为：到达 $[i, j]$ 的最小路径和由 $[i, j - 1]$ 的最小路径和与 $[i - 1, j]$ 的最小路径和中较小的那一个决定。

根据以上分析，可推出下图所示的状态转移方程：

d p [i, j] = min (d p [i - 1, j], d p [i, j - 1]) + g r i d [i, j]

NOTE

根据定义好的 $d p$ 表，思考原问题和子问题的关系，找出通过子问题的最优解来构造原问题的最优解的方法，即最优子结构。

一旦我们找到了最优子结构，就可以使用它来构建出状态转移方程。

第三步：确定边界条件和状态转移顺序

在本题中，处在首行的状态只能从其左边的状态得来，处在首列的状态只能从其上边的状态得来，因此首行 $i = 0$ 和首列 $j = 0$ 是边界条件。

如下图所示，由于每个格子是由其左方格子和上方格子转移而来，因此我们使用循环来遍历矩阵，外循环遍历各行，内循环遍历各列。

NOTE

边界条件在动态规划中用于初始化 $d p$ 表，在搜索中用于剪枝。

状态转移顺序的核心是要保证在计算当前问题的解时，所有它依赖的更小子问题的解都已经被正确地计算出来。

根据以上分析，我们已经可以直接写出动态规划代码。然而子问题分解是一种从顶至底的思想，因此按照“暴力搜索 $\to$ 记忆化搜索 $\to$ 动态规划”的顺序实现更加符合思维习惯。

2.2.1 方法一：暴力搜索

从状态 $[i, j]$ 开始搜索，不断分解为更小的状态 $[i - 1, j]$ 和 $[i, j - 1]$ ，递归函数包括以下要素。

递归参数：状态 $[i, j]$ 。
返回值：从 $[0, 0]$ 到 $[i, j]$ 的最小路径和 $d p [i, j]$ 。
终止条件：当 $i = 0$ 且 $j = 0$ 时，返回代价 $g r i d [0, 0]$ 。
剪枝：当 $i < 0$ 时或 $j < 0$ 时索引越界，此时返回代价 $+ \infty$ ，代表不可行。

实现代码如下：

/* 最小路径和：暴力搜索 */
int minPathSumDFS(vector<vector<int>> &grid, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // 返回从左上角到 (i, j) 的最小路径代价
    return min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
}

下图给出了以 $d p [2, 1]$ 为根节点的递归树，其中包含一些重叠子问题，其数量会随着网格 grid 的尺寸变大而急剧增多。

从本质上看，造成重叠子问题的原因为：存在多条路径可以从左上角到达某一单元格。

每个状态都有向下和向右两种选择，从左上角走到右下角总共需要 $m + n - 2$ 步，所以最差时间复杂度为 $O (2^{m + n})$ 。请注意，这种计算方式未考虑临近网格边界的情况，当到达网络边界时只剩下一种选择，因此实际的路径数量会少一些。

2.2.2 方法二：记忆化搜索

我们引入一个和网格 grid 相同尺寸的记忆列表 mem ，用于记录各个子问题的解，并将重叠子问题进行剪枝：

/* 最小路径和：记忆化搜索 */
int minPathSumDFSMem(vector<vector<int>> &grid, vector<vector<int>> &mem, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // 若已有记录，则直接返回
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // 左边和上边单元格的最小路径代价
    int up = minPathSumDFSMem(grid, mem, i - 1, j);
    int left = minPathSumDFSMem(grid, mem, i, j - 1);
    // 记录并返回左上角到 (i, j) 的最小路径代价
    mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
    return mem[i][j];
}

如下图所示，在引入记忆化后，所有子问题的解只需计算一次，因此时间复杂度取决于状态总数，即网格尺寸 $O (nm)$ 。

2.2.3 方法三：动态规划

基于迭代实现动态规划解法，代码如下所示：

/* 最小路径和：动态规划 */
int minPathSumDP(vector<vector<int>> &grid) {
	int n = grid.size(), m = grid[0].size();
	vector<vector<int>> dp(n, vector<int>(m));
	dp[0]][0] = grid[0][0];
	for (int i = 1; i < n; i++) {
		dp[i][0] = dp[i-1][0] + grid[i][0];
	}
	for (int j = 1; j < m; j++) {
		dp[0][j] = dp[0][j-1] + grid[0][j];	
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
		}
	}
	return dp[n-1][m-1];
}

最小路径和的状态转移过程，其遍历了整个网格，因此时间复杂度为 $O (nm)$ 。

数组 dp 大小为 $n \times m$ ，因此空间复杂度为 $O (nm)$ 。

2.2.4 空间优化

由于每个格子只与其左边和上边的格子有关，因此我们可以只用一个单行数组来实现 $d p$ 表。

请注意，因为数组 dp 只能表示一行的状态，所以我们无法提前初始化首列状态，而是在遍历每行时更新它：

/* 最小路径和：空间优化后的动态规划 */
int minPathSumDPComp(vector<vector<int>> &grid) {
    int n = grid.size(), m = grid[0].size();
    // 初始化 dp 表
    vector<int> dp(m);
    // 状态转移：首行
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 状态转移：其余行
    for (int i = 1; i < n; i++) {
        // 状态转移：首列
        dp[0] = dp[0] + grid[i][0];
        // 状态转移：其余列
        for (int j = 1; j < m; j++) {
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}

Sean's Blog

Explorer

04.动态规划

动态规划

1 动态规划的问题特性

1.1 最优子结构

1.2 无后效性

1.3 子问题重叠

2 动态规划解题思路

2.1 问题判断

2.2 问题求解步骤

2.2.1 方法一：暴力搜索

2.2.2 方法二：记忆化搜索

2.2.3 方法三：动态规划

2.2.4 空间优化

背包DP

09.插头 DP

01.动态规划基础

02.记忆化搜索

04.区间 DP

05.DAG 上的 DP

06.树形 DP

07.状压 DP

08.数位 DP

10.计数 DP

11.动态 DP

12.概率 DP

13.DP 套 DP

14.DP 优化

目录

Graph View

反向链接