故事要从我们的老朋友 DFS 说起，请你用 dfs 递归地写出程序解决一个小问题：
例题 1：牛客 54507. 小乐乐走台阶
题目描述
小乐乐上课需要走n阶台阶，因为他腿比较长，所以每次可以选择走一阶或者走两阶，那么他一共有多少种走法？
输入描述: 输入包含一个整数n (1 ≤ n ≤ 30)
输出描述: 输出一个整数，即小乐乐可以走的方法数。
样例输入 3
样例输出 3
如果你已经掌握了 dfs，你的代码大概长这样：
参考代码 1-1（DFS）
#include <bits/stdc++.h>using namespace std;int dfs(int n) {if (n == 0) {return 1;}if (n < 0) {return 0;}return dfs(n - 1) + dfs(n - 2);}int main() {int n;cin >> n;cout << dfs(n) << endl;return 0;}
别看它短，它可以让你顺利 AC，这值得庆祝。我们还是按照决策的眼光，分析我们 dfs 的决策树。
- dfs(3) ...... 3
- dfs(2) ...... 2
- dfs(1) ...... 1 [1]
- dfs(0) ...... 1
- dfs(-1) ...... 0
- dfs(0) ...... 1
- dfs(1) ...... 1 [2]
- dfs(0) ...... 1
- dfs(-1) ...... 0
发现了吗，我们在 [1]，[2] 处为了计算 dfs(1) 进行了同样的搜索，也就是我们把一件事情重复做了多次：
- dfs(1) ...... 1
- dfs(0) ...... 1
- dfs(-1) ...... 0
这意味着，我们做了无用的搜索，且这种搜索会随着数据量增加，像一棵树一样生长起来，这个浪费的计算量将是致命的！
这个问题产生的根本原因，就在于我们「决策的眼光」，我们认为作为不同的决策顺序，每一种决策排列都是不一样的，都需要进行搜索。而事实上，此题中所有的dfs(1) 是同样的问题。
我们为了解决题目 dfs(n) ，计算 dfs(n - 1) 和 dfs(n - 2)，这两个问题都是题目问题分解而成的「子问题」。这些问题拥有相同的定义，只有参数不同，可以递归求解。一旦这些子问题得到解决，题目原问题也可以得到解决。另一方面，这些子问题不受前面的决策所影响。与 dfs 例题「例题 1：百练 4103. 踩方格」不同的是，踩方格关心前置的决策使得哪些格子已经踩过；而在此题中，解决子问题只关心「剩余台阶数」这一个参数。
我们可以为这个问题做一个「备忘」，记录在不同输入时，问题的答案。每次尝试回答问题时，先查表，查不到答案再进行搜索，避免搜索「重叠子问题」。这就是「记忆化搜索」，有人也把它称为自顶向下的动态规划。
参考代码 1-2（记忆化搜索）
#include <bits/stdc++.h>
using namespace std;
const int N = 34;
int mem[N];
int dfs(int n) {
if (n == 0) {
return 1;
}
if (n < 0) {
return 0;
}
return mem[n] != 0 ? mem[n] : mem[n] = dfs(n - 1) + dfs(n - 2);
}
int main() {
int n;
cin >> n;
cout << dfs(n) << endl;
return 0;
}
像这样，使用些内存空间做记录，每个子问题只求解一次，避免了指数级别数量决策的计算。
递归思路的核心是，把问题分解成子问题，解出子问题就能求解主问题，重复分解问题，直到可以求解所有子问题。这是从问题出发的角度。
如果换一种角度，从条件出发呢？把递归的终止条件，能够解决的最小问题当做条件；把问题看成从初始状态转移至目标状态的过程，则有：
// 初始状态
mem[: 0] = 0;
mem[0] = 1
// 递推
mem[1] = mem[0] + mem[-1] = 1
mem[2] = mem[1] + mem[0] = 2
mem[3] = mem[2] + mem[1] = 3
// ...
我们有递推公式，它在动态规划问题当中被称为「状态转移方程」：
根据状态转移方程，写出程序。
参考代码 1-3（DP）
#include <bits/stdc++.h>
using namespace std;
const int N = 34;
int dp[N];
int n;
int main() {
cin >> n;
dp[0] = dp[1] = 1;
for (int i=2; i<=n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n] << endl;
return 0;
}
这就是本题的动态规划（Dynamic Programming，简称 DP） 方法。所用到的数组常常声明为 dp[]，本题中数组元素的定义就是子问题的答案。需要注意的是，子问题的定义不一定和题目问题完全一致。
看到这里，你是否觉得「什么嘛，我已经学会 DFS 了，为什么不写优雅的记忆化搜索呢！」你说的很对，递归思考通常是更加流畅，符合人的思维的。在多数情况下，如果你能确定记忆化搜索可以完成任务，你完全可以那么做，记忆化搜索可以替代大部分动态规划的递推解法。是的，也就是说，也有解决不了的时候，也有用动态规划更简明的时候。作为一个熟悉算法的程序设计选手，你也应当把 DP 作为你的新技能来学习了。因为有关 DP 的内容，才刚刚开始呢。
DP 由于基于递推，它只需要存储下一项的依赖项即可，上面例题的程序还可以把数组改写成三个变量。
参考代码 1-4（DP + 空间优化）
#include <bits/stdc++.h>
using namespace std;
const int N = 34;
int a, b, c;
int n;
int main() {
cin >> n;
a = b = 1;
for (int i=2; i<=n; ++i) {
c = a + b;
a = b;
b = c;
}
cout << c << endl;
return 0;
}
这就是 DP 常见的「空间优化」操作，也是记忆化搜索完成不了的部分。通常的空间优化是把二维 DP 数组转化为一维数组这种，减少一个维度的优化。上述三个变量的优化除非确实需要，意义不大。
例题 2：百练 1163. The Triangle
- 时间限制： 1000ms 内存限制： 65536KB
描述
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 （图1）图 1 显示了一个数字三角形。编写一个程序，计算从顶部开始到底部某处结束的路径上传递的最大数字总和。每一步都可以向左斜向下或向右斜向下。
- 输入
您的程序将从标准输入中读取。第一行包含一个整数 N：三角形中的行数。下面N行描述了三角形的数据。三角形中的行数 > 1 但 <= 100。三角形中的数字，所有整数，都在 0 到 99 之间。- 输出
您的程序将写入标准输出。最高和写为整数。- 样例输入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
- 样例输出
30
还是按照递归的思路，搜索每一步决策：
可以写出 DFS 的代码。
参考代码 2-1（DFS）
#include <bits/stdc++.h>
using namespace std;
const int N = 104;
int a[N][N];
int n;
int dfs(int r, int c) {
if (r == n) {
return a[n][c];
}
return a[r][c] + max(dfs(r + 1, c), dfs(r + 1, c + 1));
}
int main() {
cin >> n;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=i; ++j) {
cin >> a[i][j];
}
}
cout << dfs(1, 1) << endl;
return 0;
}
这一代码有大量的重复计算，运行结果是超时。我们可以将它改写成记忆化搜索。由于要记录的最大值可能是 0 ，初始化记忆化数组为一个无意义的值 -1。
参考代码 2-2（记忆化搜索）
#include <bits/stdc++.h>
using namespace std;
const int N = 104;
int a[N][N];
int mem[N][N];
int n;
int dfs(int r, int c) {
if (r == n) {
return a[n][c];
}
if (mem[r][c] != -1) {
return mem[r][c];
}
return mem[r][c] = a[r][c] + max(dfs(r + 1, c), dfs(r + 1, c + 1));
}
int main() {
cin >> n;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=i; ++j) {
cin >> a[i][j];
mem[i][j] = -1; // 初始化
}
}
cout << dfs(1, 1) << endl;
return 0;
}
接下来我们尝试动态规划的递推方式。
从递归逻辑中，我们看到突破点其实是三角形的最底层。递归到最底层后，程序才能一层一层向上算出上一层问题的结果，最终算出题目问题的答案。
递推的思路是，先查看最底层。查看倒数第二层时，确定可选择的最底层的最大的数，加上倒数第二层本身的数，作为倒数第二层的答案。我们相当于在填写记忆化搜索中的备忘数组。像这样在纸上演算，模拟递推过程是动态规划思考常用的方法。
原数组： 递推数组：
7 30
3 8 23 21
8 1 0 20 13 10
2 7 4 4 7 12 10 10
4 5 2 6 5 4 5 2 6 5
根据填写数组的逻辑，我们有状态转移方程：
写出动态规划的代码如下：
参考代码 2-3（DP）
#include <bits/stdc++.h>
using namespace std;
const int N = 104;
int dp[N][N];
int n;
int main() {
cin >> n;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=i; ++j) {
cin >> dp[i][j];
}
}
for (int i=n; i>=1; --i) {
for (int j=1; j<=i; ++j) {
dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);
}
}
cout << dp[1][1] << endl;
return 0;
}
或许你已经发现，dp 也有它独特的美感。代码中直接使用了 dp 数组替换原数组，这是因为，在 dp 数组当前位置更新时，用到 dp 数组当前位置的值尚未被更新，这个值就是初始读入的原数组的值。
注意更新 dp 数组的两重 for 循环， 倒序遍历， 每次用到它的更下一层，这个顺序不能颠倒。dp 的思想在于，每次从已知的状态转移而来，更新到下一个状态。也就是说，更新 dp 数组所用到的值，一般来说必须是已经更新过的（除非没有更新过的值才是需要用到的状态的值）。
你可能注意到第一轮更新访问到数组的第 行，但其实并不影响，我们的数组开得足够大，不会造成越界。而数组的默认值
不影响我们得出正确的结果。总而言之，将数组开大一圈，多出的
值常常方便我们少写很多边界判断的条件。
接下来演示空间优化操作。在题目复杂、数据量大时，空间优化有时会越来越有必要。
再次检查上述算法，我们没有必要存储整个二维 dp 数组，每一层的递推只依赖最近的下一层。我们直接重复利用一维数组，或称为「滚动数组」。我们必须保留原数组，用以实现递推（你可以重温填数字的过程）。这样，你可能会发现，总体的空间复杂度反而上升了，但是我们专用做 dp 计算的空间开销减少了。在题目需要保留原数组做其他操作时，这种方法的空间复杂度的是更优的。
参考代码 2-4（DP + 空间优化）
#include <bits/stdc++.h>
using namespace std;
const int N = 104;
int a[N][N];
int dp[N];
int n;
int main() {
cin >> n;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=i; ++j) {
cin >> a[i][j];
}
}
for (int j=1; j<=n; ++j) {
dp[j] = a[n][j];
}
for (int i=n-1; i>=1; --i) {
for (int j=1; j<=i; ++j) {
dp[j] = a[i][j] + max(dp[j], dp[j + 1]);
}
}
cout << dp[1] << endl;
return 0;
}
时间复杂度：#card=math&code=O%28n%5E2%29&id=QZQnE)
总结：动态规划问题的一般思路
1. 划分子问题
- 把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决。
- 子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。
2. 确定状态定义
- 在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个状态。一个状态对应于一个或多个子问题， 所谓某个状态下的值，就是这个状态所对应的子问题的解。
- 如何定义一个状态表示什么子问题、一个状态下的值表示什么含义至关重要。
3. 确定一些初始状态（边界状态）的值
- 递推从一组确定的初始状态，一步一步向最终答案的状态转移。这个初始状态常常就是递归方法中的终止条件。
4. 确定状态转移方程
- 状态转移方程根据状态的定义，明确指出状态转移的计算方法，其计算的依赖关系也暗示着遍历数组的顺序。
总结：能用动态规划解决的问题的特点
1. 问题具有最优子结构性质
- 如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结构性质。
2. 无后效性
- 当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态没有关系。
参考：中国大学MOOC 程序设计与算法（二）算法基础 讲义
如上，我们从 DFS 到 DP，一步步地介绍了动态规划算法。动态规划的思想是十分重要的算法思想，它能够避免枚举所有可能的决策，极大降低时间和空间复杂度，从而解决很多复杂的问题。下面将介绍一些经典的动态规划问题。
若有收获，就点个赞吧
0 人点赞
