动态规划算法DP
动态规划，Dynamic Programming，简称 DP。
动态规划并不是某一种固定算法，而是一种解决问题的方法。
很多问题如果直接使用递归，会重复计算大量相同的子问题。动态规划的核心就是：
将已经计算过的结果保存下来，在以后需要的时候直接使用，而不是重新计算。
简单来说就是：
大问题
↓
分成若干小问题
↓
保存小问题答案
↓
利用小问题答案推出大问题答案DP 最重要的不是把代码背下来，而是找到：
状态
状态转移方程
初始状态
计算顺序一个最简单的例子
先从 Fibonacci 数列开始。
定义：
F(1) = 1
F(2) = 1以后：
F(n) = F(n-1) + F(n-2)如果直接递归：
int fib(int n)
{
if (n <= 2)
return 1;
return fib(n - 1) + fib(n - 2);
}虽然写起来非常简单，但是这里存在大量重复计算。
例如：
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2)
│ │ └── fib(1)
│ └── fib(2)
└── fib(3)
├── fib(2)
└── fib(1)可以看到：
fib(3)
fib(2)
fib(1)会被计算很多次。
实际上同一个：
fib(3)不管调用多少次，答案都不会发生变化。
既然如此，就没有必要重复算。
使用数组保存状态
定义：
int f[1000];令：
f[1] = 1;
f[2] = 1;然后：
for (int i = 3; i <= n; i++)
{
f[i] = f[i - 1] + f[i - 2];
}完整代码：
#include <cstdio>
int f[1000];
int main()
{
int n;
scanf("%d", &n);
f[1] = 1;
f[2] = 1;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
printf("%d\n", f[n]);
return 0;
}这里：
f[i]就是一个状态。
而：
f[i] = f[i-1] + f[i-2]就是状态转移方程。
什么是状态
DP 中最重要的问题往往不是：
代码怎么写？
而是：
f[i]到底表示什么？
如果连状态代表什么都没有定义清楚，后面的状态转移基本不可能正确。
例如刚才：
f[i]可以定义为：
Fibonacci 数列第 i 项的值。
那么：
f[i-1]和：
f[i-2]分别表示前一项和前两项。
根据问题本身的规律：
f[i] = f[i-1] + f[i-2]于是整个 DP 就成立了。
所以做 DP 时最好先写一句：
f[i] 表示……或者：
f[i][j] 表示……再继续想状态转移。
动态规划基本步骤
一般可以按照下面的顺序考虑。
1. 定义状态
例如：
f[i]表示前 i 个元素的最优答案。
或者：
f[i][j]表示处理到第 i 个位置，并且当前具有状态 j 时的答案。
不同题目的状态含义完全不同。
2. 找状态转移方程
也就是：
当前状态可以从哪些以前已经计算出的状态转移过来？
例如：
f[i] = max(f[i-1], f[i-2] + a[i])又或者：
f[i][j] = max(
f[i-1][j],
f[i-1][j-w[i]] + v[i]
)真正困难的通常就是这一部分。
3. 初始化
例如：
f[0] = 0;或者：
f[1][1] = a[1][1];如果初始状态错误，后面所有结果都会跟着错误。
4. 确定计算顺序
DP 的当前状态必须建立在：
已经算出来的状态之上。
所以遍历顺序很重要。
例如有些题：
i 从小到大有些背包问题：
j 必须从大到小如果顺序写反，状态就可能被当前这一轮重复使用。
数字三角形
来看一个比较典型的 DP。
例如：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5从最上方开始，每一步只能走到下一行相邻的位置。
求走到底部时经过数字的最大和。
状态定义
令：
f[i][j]表示：
从三角形顶部走到第 i 行第 j 个位置时，可以得到的最大数字和。
当前：
(i, j)只可能从上一行两个位置走过来：
(i-1, j-1)或者：
(i-1, j)所以：
f[i][j]
=
max(
f[i-1][j-1],
f[i-1][j]
)
+
a[i][j]这就是状态转移方程。
边界
三角形左右两侧需要单独注意。
可以直接把整个数组初始化为一个很小的数。
或者根据：
j = 1
j = i单独处理。
对于入门来说，可以直接写得清楚一点。
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1005][1005];
int f[1005][1005];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
f[1][1] = a[1][1];
for (int i = 2; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
if (j == 1)
{
f[i][j] = f[i - 1][j] + a[i][j];
}
else if (j == i)
{
f[i][j] = f[i - 1][j - 1] + a[i][j];
}
else
{
f[i][j] =
max(
f[i - 1][j - 1],
f[i - 1][j]
)
+ a[i][j];
}
}
}
int ans = 0;
for (int j = 1; j <= n; j++)
ans = max(ans, f[n][j]);
printf("%d\n", ans);
return 0;
}这就是一个标准的：
二维 DP01背包
背包问题应该算是动态规划中最经典的一类问题。
现在有：
n 个物品每个物品有：
重量 w[i]
价值 v[i]背包最大容量：
m每个物品只能选择：
0次
或
1次问可以获得的最大价值。
这就是：
01背包二维状态
先定义：
f[i][j]表示：
只考虑前 i 个物品，背包容量为 j 时能够取得的最大价值。
对于第：
i个物品，我们只有两种选择：
不选或者：
选不选第 i 个物品
那么：
f[i][j] = f[i-1][j]选择第 i 个物品
首先必须满足：
j >= w[i]选择以后，需要给它留下：
w[i]的容量。
所以之前只能够使用：
j - w[i]容量。
因此：
f[i][j]
=
f[i-1][j-w[i]]
+
v[i]两种选择取最大值
最终：
f[i][j]
=
max(
f[i-1][j],
f[i-1][j-w[i]] + v[i]
)这就是 01 背包最基本的状态转移方程。
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int w[1005];
int v[1005];
int f[1005][1005];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if (j >= w[i])
{
f[i][j] =
max(
f[i][j],
f[i - 1][j - w[i]] + v[i]
);
}
}
}
printf("%d\n", f[n][m]);
return 0;
}一维优化
上面的状态：
f[i][j]实际上只使用了：
f[i-1][...]这一行。
也就是说：
第 i 行算完以后：
第 i-2 行已经没有用了。
因此可以把：
二维数组优化成：
一维数组定义：
f[j]表示当前处理过的物品中，在容量为 j 时能够取得的最大价值。
状态转移：
f[j]
=
max(
f[j],
f[j-w[i]] + v[i]
)代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int w[1005];
int v[1005];
int f[10005];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= w[i]; j--)
{
f[j] =
max(
f[j],
f[j - w[i]] + v[i]
);
}
}
printf("%d\n", f[m]);
return 0;
}注意这里：
for (int j = m; j >= w[i]; j--)容量必须：
从大到小遍历。
为什么01背包要倒序
这是背包 DP 中很容易搞错的一点。
假设：
w[i] = 2
v[i] = 3如果从小到大计算：
f[2] = f[0] + 3然后继续：
f[4] = f[2] + 3但这里的：
f[2]已经在本轮使用第 i 个物品更新过了。
那么：
f[4]实际上就相当于把第 i 个物品使用了：
2次这违反了：
01背包每个物品只能选择一次的条件。
所以必须：
从大到小更新。
这样使用：
f[j-w[i]]的时候，它仍然是：
上一轮留下来的结果。
完全背包
如果题目修改一下：
每种物品可以选择无限次。
那么就是：
完全背包状态转移其实仍然可以写成：
f[j]
=
max(
f[j],
f[j-w[i]] + v[i]
)但是遍历顺序改变：
for (int i = 1; i <= n; i++)
{
for (int j = w[i]; j <= m; j++)
{
f[j] =
max(
f[j],
f[j - w[i]] + v[i]
);
}
}这里容量：
从小到大遍历。
为什么？
因为完全背包允许：
同一个物品继续使用所以当前这一轮刚刚更新的：
f[j-w[i]]可以继续参与后面的计算。
于是：
01背包
容量倒序而：
完全背包
容量正序这是最基本的区别之一。
最长上升子序列
再来看一种和背包完全不同的 DP。
给出一个序列：
3 1 2 5 4需要寻找一个：
严格递增的子序列，使长度最大。
例如：
1 2 5长度为：
3或者：
1 2 4长度也是：
3这就是：
Longest Increasing Subsequence简称：
LIS状态定义
令：
f[i]表示：
以第 i 个元素作为结尾的最长上升子序列长度。
那么对于：
j < i如果：
a[j] < a[i]说明第 i 个元素可以接到：
以 j 结尾的上升子序列后面。
所以：
f[i]
=
max(
f[i],
f[j] + 1
)初始化：
f[i] = 1因为即使前面一个元素都接不上：
a[i]自己也能组成长度为 1 的序列。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1005];
int f[1005];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = 0;
for (int i = 1; i <= n; i++)
{
f[i] = 1;
for (int j = 1; j < i; j++)
{
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}
ans = max(ans, f[i]);
}
printf("%d\n", ans);
return 0;
}这里时间复杂度为：
O(n²)虽然 LIS 还可以继续优化，但先理解这个 DP 写法更加重要。
DP和递归
很多动态规划其实都可以先写成递归。
例如：
f(n)不断调用：
f(n-1)
f(n-2)这种写法一般称为：
自顶向下如果再加一个数组，把已经计算过的答案保存起来：
if (f[n] != -1)
return f[n];就变成：
记忆化搜索例如：
int f[1000];
int solve(int n)
{
if (n <= 2)
return 1;
if (f[n] != -1)
return f[n];
return f[n] = solve(n - 1) + solve(n - 2);
}它和普通 DP 的思想其实是一致的：
不重复计算已经求过的状态。
区别主要在于：
记忆化搜索
=
从目标状态向下递归
递推DP
=
从已知状态逐步向上计算很多题两种方法都能写。
DP最难的地方
动态规划真正难的从来不是：
for
max
数组这些代码。
最难的是：
状态怎么定义？以及：
状态之间有什么关系？例如看到一道题：
求最大值并不能直接判断：
这就是DP而应该观察：
- 一个大问题能不能拆成更小的问题；
- 不同大问题之间是否会重复使用相同的小问题；
- 一个问题的最优答案是否能够由更小问题的最优答案得到；
- 能不能设计一个有限的状态来表示已经处理的信息。
如果可以，才应该考虑动态规划。
常见DP状态
OI 中经常能看到一些类似的形式。
例如：
f[i]处理到位置 i 时的答案。
f[i][j]处理前 i 个元素，在条件 j 下的答案。
f[i][j][k]处理到某个位置，并同时记录另外两个状态。
状态越多：
时间
空间一般都会增加。
所以并不是状态写得越复杂越好。
应该只记录：
对未来决策真正有影响的信息。
时间复杂度
DP 并不代表：
一定很快例如一个：
f[i][j]如果：
i <= 10000
j <= 10000那么状态数量已经达到：
10^8如果每个状态还需要：
O(n)转移，就更加无法接受。
一般可以粗略理解：
DP时间复杂度
≈
状态数量
×
每个状态的转移数量例如数字三角形：
状态数 O(n²)
每个状态 O(1) 转移
总复杂度 O(n²)LIS 的普通写法：
状态数 O(n)
每个状态枚举 O(n)
总复杂度 O(n²)所以设计状态以后，还应该检查：
这个 DP 跑得完吗？
空间优化
很多 DP 状态只依赖：
上一层例如：
f[i][j]只需要：
f[i-1][...]这时没有必要保留以前所有层。
可以使用：
滚动数组甚至像 01 背包一样直接压缩成：
一维数组因此：
二维DP并不一定真的要开二维数组。
但是刚开始学习时，不应该为了省几个数组元素就把状态压得完全看不懂。
最好先：
把正确的二维DP写出来理解状态转移以后，再考虑优化。
总结
动态规划最核心的部分可以概括为：
定义状态
↓
寻找状态之间的关系
↓
写出状态转移方程
↓
确定边界和初始状态
↓
确定正确的计算顺序
↓
得到最终答案常见形式包括：
线性DP
背包DP
区间DP
树形DP
数位DP
状态压缩DP但这些分类并不是最重要的。
不管以后遇到什么 DP，最先问的都应该是：
f 到底表示什么？然后再问：
当前的 f 可以从哪里转移过来？只要这两件事情想清楚，代码通常就已经写完一半了。
最后记住：
DP 不是公式的集合，而是一种把重复子问题保存下来，再利用已经得到的答案推导新答案的方法。
这一切，似未曾拥有