动态规划 – Introduction

随便扯扯

统计一下 LeetCode 周赛从第 173 场到第 141 场中共 32 道 Hard 题（144 场没有 Hard），能够得到一个非常直观的信息，那就是熟练掌握动态规划就能大概率切掉 LeetCode 周赛的 Hard 题。

算法	题数	所占百分比	比赛场次
动态规划	14	43.75%	173、172、171、170、165、164、160、159、157、153、148、147、145、141
图论	5	15.625%	167、163、156、155（拓扑）、154（割边）
搜索	2	6.25%	169、166
位运算	2	6.25%	162、152
数据结构	2	6.25%	151、149
表达式计算	2	6.25%	143、142
模拟	1	3.125%	168
数学	1	3.125%	161
分类讨论	1	3.125%	158
后缀数组	1	3.125%	150
曼哈顿距离转化	1	3.125%	146

为什么钟意将动态规划作为周赛的 Hard 题目呢，我认为以下几点原因：

灵活：动态规划题目中类型丰富，套路代码较少，专杀 “过拟合的神经网络” 们！
质量：问题中的阶段划分、状态设计、状态之间转移以及一些边界都是需要自己思考的
简单：代码量不高，想到 合适的思路 后可以快速实现，字里行间都能体现出水平

正因如此它，能够在短时间内体现出一个人有条理地分析问题、解决问题的能力。另外，还有很重要一点，动态规划那套逻辑其实很 “计算机”，任意一个问题想要使用计算机解决，无非就是先向问题怎么使用计算机表示，然后如何运算得到结果，这就对应了动态规划里的状态表示与状态转移。一个人动态规划掌握得好，那么他的计算机思维同样应该很不错。
所以，现在动态规划是很多科技公司机试、面试，保研、考研夏令营机试大概率出的一类算法题，而且属于较难的那部分。

基本术语

学习动态规划之初，我们需要先明确一些基本概念，统一一下术语。

动态规划：运筹学中的一个分支，是求解决策过程最优化的数学方法。
阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段。
状态：状态表示每个阶段开始面临的自然状况或客观条件。
决策（转移）：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择称为决策。
策略：每阶段都做一个决策，一系列决策的集合。
边界：初始集合。

先说动态规划的状态设计，其实包含两步：阶段划分与状态设计，这两部分的关系又非常紧密，所以面对问题的时候放在一起思考，统称为状态设计。简单来说，我们把原问题划分成若干个不相交的部分，这每一个部分就是一个阶段，而具体看每一个阶段的时候，需要一些信息来刻画阶段中不同的情况。不同的情况就是状态，刻画情况的信息就是状态的表示。

这样看上去，阶段和状态似乎没有什么区别，都是用来描述问题不同情况的。这时候就需要决策上场了。决策，对应动态规划中的状态转移，一个决策可以从一个阶段的状态演变到另一个不同阶段的状态中去，如果将阶段看成是点，决策看成是连在阶段间的有向边，那么这两个东西一定组成的是一个 DAG（有向无环图）。这也是保证了动态规划问题的优秀复杂度，即同一个状态不会直接 / 间接的更新自己。

边界看上去没啥好说的，就是问题中你能够轻易知道答案的状态，我们把它叫做初始状态，动态规划的过程一般从初始状态开始向后进行。

这样说起来，很是抽象，我们举一个简单的例子，并用动态规划的方法来分析这件事情。
吃完饭，WNJXYK 想要和 VineAsh 一起去看电影。那么他要处理几个问题：

电影票：他可以出发前网上订票 / 到电影院现场买票
清洁餐具：出发前洗碗 / 看电影后回家洗碗

第一，先寻找怎么划分阶段，也就是上图中的几个标题大字。因为都是真实发生的事件，所以可以按照事件发生的时机（时间点 / 时间段）划分，有 4 个阶段：吃完饭、出发前、到达电影院、看完电影后。因为按照阶段的划分是按照时序的，所以只能从前向后发展，这就保证了阶段与转移形成一个 DAG。

第二，来分析状态，也就是上图中的圆圈。问题中洗没洗碗与定没定票，决定了在某一个阶段的状态时，可以向下一个阶段的哪些状态进行转移（与怎么转移），所以状态表示就是是否洗碗 $\times $ 是否订票，分别对应图中：

A：没订票也没洗碗
B：没订票但洗了碗
C：定了票但没洗碗
D：没订票也没洗碗

第三，确定状态转移，也就是连接圆圈之间的有向箭头。因为分析的是生活例子，所以状态转移几乎同 WNJXYK 处理问题时的操作一一对应，也在下图中列出了。
第四，初始状态，也就是状态 S，这个也是由问题确定的。

那么一个策略可以是：S->橘D->蓝D->绿D，也可以是 S->橘C->蓝C->绿D 或者其他。

至此，你应该已经理解了如何阶段、状态、决策、边界，策略这几个名词的意义。

动态规划问题性质

接下来，我们了解三个动态规划状态需要满足的性质：

最优子结构：一个最优化策略的子策略总是最优的，反过来，我们可以通过最优的子策略，推出最优策略。
无后效性：当我们通过一系列策略到达了某一阶段的某一状态时，下一步决策不受之前的一系列策略影响，仅由当前状态决定。
子问题重叠：算法计算的过程中会反复地求解相同的一定量的子问题，而不是不断生成没有见过的新问题。也就是说子问题空间不大，或是状态空间不大，我们可以通过存储状态的答案加快计算速度。

拿动态规划的经典问题数塔来举例子：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

首先考虑上一节所说的状态表示与转移，我们先找一组符合动态规划要求性质的表示与转移：

阶段：数塔的每一层就是一个阶段，转移的时候，从上一层向下一层转移。
状态：位于数塔每一层的那个节点就是状态，因为每一步只能走到相邻的节点，所以状态决定了能够向下一阶段的哪些状态转移。
状态转移：由题目中 每一步只能走到相邻的结点 得到，状态转移就是上一层节点向下一层相邻节点转移。
初始状态：由题目中得到，数塔顶部节点。

如此，我们的可以由阶段和状态得到：

状态表示：$dp[i][j]$ 表示位于第 $i$ 层第 $j$ 个元素的最大数字之和
状态转移即为 $dp[i][j] = \max(dp[i-1][j-1], dp[i-1][j]) + v[i][j]$
初始状态为 $dp[1][1] = 9$。

对照着性质一条一条看，分析以下动态规划的性质：

如果我们当前在状态 $(i,j)$（即第 $i$ 行第 $j$ 列，下同），我们只能从状态 $(i-1,j-1)$ 与状态 $(i-1,j)$ 走过来，$(i,j)$ 的最优决策一定能由它的两个子决策 $(i-1,j-1)$ 与 $(i-1,j)$ 推导出来，这就满足了最优子结构性质。反应到状态转移方程中，我们就可以放心的令 $dp[i][j] = \max(dp[i-1][j-1], dp[i-1][j]) + v[i][j]$。（因为不关系具体决策序列，只关心结果，我们将最优决策得到的数字之和存储与 $dp$ 数组中）

当我们在状态 $(i,j)$ 的时候，我们考虑状态 $(i-1,j-1)$ 或状态 $(i-1,j)$ 走过来，无需在多考虑之前是怎么走到 $(i-1,j-1)$ 或是 $(i-1,j)$ 的，这就是无后效性。其实，后效性这东西和状态表示是密切相关的，如果你发现你的状态表示存在后效性，那么把没考虑的东西加入状态表示中去，那么这个后效性的就消除了。解决动态规划问题的时候，我们需要寻找一个满足无后效性的最简状态表示。

整个问题的子问题其实只有 $\frac{n(n+1)}{2}$ 种，子问题空间有限，是 $O(n^2)$ 级别的。

然后，我们看两种反面教材：

状态表示为 $dp[i]$ 表示位于第 $i$ 层的最大数字之和，这种状态表示具有后效性，因为我们从上层往下层转移的时候，因为受到题中移动的相邻节点限制且状态中不知道相邻信息，没办法直接通过 $dp[i-1]$ 转移到 $dp[i]$。我们需要多记录一维层内位置来消除后效性。

状态表示为 $dp[a,b,c,d,e]$ 第一层走节点 a，第二层走节点 b，……，第五层走节点 e 的最大数字和。状态唯一的表示了每一种数塔行走的情况，不存在子问题重叠了，这样子问题数量增加至 $n!$，无法接受。

将题目更改为求从上向下的数字路径上的最大值最小值之差的最小值，那么使用 $dp[i][j]$ 表示走到第 $i$ 层第 $j$ 个元素的最大值最小值之差就不符合最优子结构了，即使 $(i,j)$，只能从状态 $(i-1,j-1)$ 与状态 $(i-1,j)$ 走过来且 $(i-1,j-1)$ 与 $(i-1,j)$ 最优，我们也无法通过 $(i-1,j-1)$ 与 $(i-1,j)$ 的结果推出 $(i,j)$ 的最优决策，想想这是为什么~

假设下图的情形，我们不考虑其他节点的值（假设其他都不是最优的），对于状态 $(4,2)$，两种路径：$[10, 14, 14, 10]$ 的差为 $4$，$[10, 13, 8, 10]$ 的差为 $5$，显然最优决策为橙色箭头标识。状态 $(5,2)$ 的数字为 $8$，从 $(4,2)$ 的最优决策 $[10, 14, 14, 10]$ 转移过来，显然不如从非最优决策 $4$，$[10, 13, 8, 10]$ 转移。（$[10, 14, 14, 10, 8]$ 差为 $6$，$[10, 13, 8, 10, 8]$ 差为 $5$）此状态的最优策略并非从子最优决策推得，反而是从非最优子决策得到的，这就是不符合最优子结构性质。

一般来说，求最大值、最小值这种目标式单调的问题，最优子结构性质是符合的，求什么绝对值、标准差、差值之类的，前期结果雪崩，到最后一步力挽狂澜的问题，最优子结构不能符合。

动态规划题目特点

动态规划原本是用来解决求最值这类的最优化问题的，后人将其原理直接应用于计数、存在性判定（本质上也是计数）一类的问题也能够 work，所以如果你看到最值、计数、存在性判定这三类问题，不妨思考一下使用动态规划来解决。

再看数塔问题，同样要求从顶层走到底层，若每一步只能走到相邻的结点，最值就是求走出一条路径的最大数字和是多少，计数可以是求走出一条路径数字和不超过 55 的方案数，存在性判定可以是求是否存在一条路径的数字和等于 55。

动态规划代码实现

两种写代码的方式：记忆化搜索与递推。我认为记忆化搜索是一种相对容易理解好上手的代码方式，递推需要考虑更多的东西，优点是支持加入各种高级优化。

先说记忆化搜索，我认为这是一个相对简单的动态规划实现方法。它可以理解为在我们确定的状态上进行搜索，然后通过一个额外的数组保存每一个状态的答案，搜索某一个状态时，如果答案计算过就直接返回，否则继续向下搜索并保存计算过的答案！所以，点了搜索技能点的同学可以快速转型到记忆化搜索，它的好处有以下几点：

能避免计算一些根本用不到的状态。
决策边界容易考虑，搜不下去就是边界。
减少思考量，不用考虑状态之间的计算顺序，程序只需要立足当前状态与当前状态的子状态即可。
实现容易，写出搜索，加个记忆化就完事了。
可以使用搜索的奇技淫巧优化。

因为记忆化搜索存在一个搜索的框架，所以可以写出一个比较抽象的模板：

int dp[状态表示];
int dfs(状态表示) {
    if (决策边界) return 决策边界答案; // 决策边界
    if (dp[状态表示] != 无效数值) return dp[状态表示]; // 记忆化
    for (当前状态表示的 子状态) dfs(子状态) 更新 dp[状态表示]; // 状态转移
    return dp[状态表示];
}
int solve() {
    memset(dp, 无效数值, sizeof(dp));
    return dfs(原问题状态);
}

int dp[状态表示];

int dfs(状态表示) {

if (决策边界) return 决策边界答案; // 决策边界

if (dp[状态表示] != 无效数值) return dp[状态表示]; // 记忆化

for (当前状态表示的子状态) dfs(子状态) 更新 dp[状态表示]; // 状态转移

return dp[状态表示];

}

int solve() {

memset(dp, 无效数值, sizeof(dp));

return dfs(原问题状态);

}

再讲递推，简单了说是使用 For 循环嵌套对所有状态进行枚举，使用转移方程更新状态。

这里枚举状态的顺序就有讲究了，比如我们更新状态 A，需要状态 B、C、D 的答案，那么状态 B、C、D 肯定要先于状态 A 被我们枚举到，换句话说，确定状态 A 的时候，状态 B、C、D 必须已经被确定完了。一般来说，我们按照阶段地顺序枚举状态就可以了，但是很多时候问题情况比较复杂，按照阶段未必时最简单最容易实现的方法，所以枚举状态的顺序需要仔细思考。虽然，递推的实现方法相对记忆化搜索困难，但是他也有优点：

可以加入各种动态规划优化
没有记忆化搜索中系统栈的开销，速度较快

解决动态规划问题总结

说了这么多，动态规划的核心就是状态表示，我们要确定一个既不是那么复杂导致超时，又不过于简单产生后效性的合理状态表示。有了一个合理的状态表示之后，转移方程、决策边界和代码实现都是稍加思考就能得到了。

Step 1 确定状态表示，包含阶段划分与状态表示
Step 2 写出转移方程：帮助你想清楚状态之间到底是如何转移的
Step 3 确定边界：初始 Cases！
Step 4 如果使用递推，考虑一下子状态枚举的顺序。

另外，一件重要的事情是：想清楚了再写代码、想清楚了再写代码、想清楚了再写代码！

做道例题：64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

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

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

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

输入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

先确定状态表示，这道题目里的阶段比较隐式，它是斜过来在对角线上的元素。想想为什么，阶段 1 是从距离起点 0 步的位置，阶段 2 是距离起点 1 步的位置……我们总是从上一个阶段的状态向下一个阶段的状态进行更新。

那么，在每一个阶段中，我们需要知道它的具体位置，即斜线上的第几个，我们可以令 $dp[i][j]$ 表示在阶段 i 位于从上向下第 j 个的最小路径和。这样定义状态是可以将此题做出来的，但是会带来很多实现上的麻烦。
我们也可以令 $dp[i][j]$ 表示位于网格第 i 行第 j 列的最小路径和，这样阶段等于 $i + j$，依旧能隐式地表示阶段。、

状态转移方程，由题目中 每次只能向下或者向右移动一步 这句话得到，也就是 $(i, j)$ 可以从 $(i-1, j)$ 与 $(i, j-1)$ 走过来，那么转移方程就是 $dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]$。

决策边界，棋盘只有一个起点，所以 $dp[0][0] = grid[0][0]$。如果超出棋盘，也是不行的。

记忆化搜索的代码：

class Solution {
public:
    int dp[550][550];
    vector<vector<int>> grid;

    int dfs(int x, int y) {
        // 搜不下去就是边界
        if (x == 0 && y == 0) return grid[0][0];
        if (x < 0 || y < 0) return 2100000000;

        // 记忆化
        if (dp[x][y] != -1) return dp[x][y];

        // 状态转移
        dp[x][y] = min(dfs(x - 1, y), dfs(x, y - 1)) + grid[x][y];
        return dp[x][y];
    }
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        this->grid = grid;

        memset(dp, -1, sizeof(dp));
        return dfs(n - 1, m - 1);
    }
};

class Solution {

public:

int dp[550][550];

vector<vector<int>> grid;

int dfs(int x, int y) {

// 搜不下去就是边界

if (x == 0 && y == 0) return grid[0][0];

if (x < 0 || y < 0) return 2100000000;

// 记忆化

if (dp[x][y] != -1) return dp[x][y];

// 状态转移

dp[x][y] = min(dfs(x - 1, y), dfs(x, y - 1)) + grid[x][y];

return dp[x][y];

}

int minPathSum(vector<vector<int>>& grid) {

int n = grid.size(), m = grid[0].size();

this->grid = grid;

memset(dp, -1, sizeof(dp));

return dfs(n - 1, m - 1);

}

};

如果想要使用递推，我们还需要考虑枚举状态的顺序，这里可以从向往下枚举，从左往右枚举，因为一个更新一个状态，需要它左侧与它上边状态的答案，如此枚举可以保证一个状态在被更新时，他需要的状态已经被更新完毕了。而决策也相对更难考虑，在递推中做不到像搜索那样，搜不下去就是边界，我们需要人为地将第 0 行与第 0 列的元素都都作为决策边界。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dp[n][m] = {0};

        // 决策边界
        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];
    }
};

class Solution {

public:

int minPathSum(vector<vector<int>>& grid) {

int n = grid.size(), m = grid[0].size();

int dp[n][m] = {0};

// 决策边界

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

}

};

Take Home Message

动态规划以状态表示为核心，需要确定转移方程与边界情况
满足三条基本性质：最优子结构、无后效性、子问题重叠
解决最值、计数、存在性判定三类问题
使用记忆化搜索或递推地方式实现

Q&A

Q1：如何提升动态规划能力？
A1：两个办法：练习与积累。(a) 多做题，锻炼用状态描述问题，转移解决问题地思维。(b) 通过了解经典的动态规划类型，积累状态表示与转移的经验。

Q2：动态规划边界情况总是弄不清楚怎么办？
A2：(a) 想清楚了再写代码 (b) 用记忆化搜索的实现方式 (c) 强迫自己在纸上写出一些内容

mp

签到成功！签到时间:9:32:39 PM每日打卡，生活更精彩哦~

4年前 1 0 回复
geekxbr

文章一处有笔误: “当我们在状态 (i,j)(i,j) 的时候，我们考虑状态 (i-1,j-1)(i−1,j−1) 或状态 (i-1,j)(i−1,j) 走过来，无需在多考虑之前是怎么走到 (i-1,j-1)(i−1,j−1) 或是 (i-1,j-1)(i−1,j−1) 的” // 最后处打重复了

4年前 2 1 回复
万物

太厉害了！每节课听一遍看一遍再去看一道题马上学会了！话说马上要开数据结构的课，和这个有什么区别么？？？

4年前 0 1 回复
- WNJXYK
  
  相辅相成吧，数据结构更偏向于研究如何快速维护一堆数据支持增删改查，算法是给你一个问题如何高效解答，动态规划就属于一大类算法。
  
  4年前 0 0 回复
  - 万物
    
    明白了！
    
    4年前 0 0 回复
sukidayo

b站前来资瓷,感觉动态规划好难啊,一直get不到点…

4年前 2 0 回复
蓝胖

「计数可以是求走出一条路径数字和不超过 55 的方案数」
如果最大路径和不是55的话，这个计数问题可以用 dp 求解吗？OωO

3年前 0 0 回复
- 喂你脚下有坑
  
  可以呀，这个问题其实同最大路径和没有关系。路径和超过55的那些路径，我们就完全没必要考虑（因为数字都是正数，路径和之后只能更大了），对应的状态也可以无视了。
  
  3年前 0 0 回复

WNJXYKの博客

喂你脚下有坑