DP 概述
DP 问题在 OIer 中很受欢迎，因为每个 DP 问题在某种意义上都是原创的，你必须思考其状态和状态转移方程才能为其发明解决方案。
DP，是一种基于分治，将原问题分解为简单子问题求解复杂问题的方法。
动态规划的耗时往往远少于朴素解法。
动态规划 / 递归
DP 可以被描述为一种通常基于问题的起始状态，以及连续状态之间的递归公式或关系的问题解决算法。
之前说过，动态规划也是分治思路，而递归也是传统的分治思路，而 DP 又是基于递归式求解的，但时间复杂度却相差很多，为什么呢？
动态规划是自底向上思想，而递归是自顶向下解法。
自底向上 / 自顶向下？
自底向上
意思很简单，从下往上推导：。
这也是为什么动态规划脱离了递归的函数，改用循环迭代推到的原因。
自顶向下
反过来，自顶向下就是从上往下推，触底后在将结果返回。
这也是为什么递归比动态规划时间复杂度高的多的原因。
我们可以看出，动态规划更像是递归算法的加强版。
状态的定义
前言：空间换时间
很简单的名字，即为使用空间的代价来确保不会超时。
定义状态
状态，通俗来讲就是你 代表的是什么。比如斐波那契数列中 代表的就是第 位是什么。
对于状态：
状态越多，表示的信息越多，空间越大。
反之，状态越少，表示的信息越少，空间越小。
在我们状态定义时，可能有这些情况：
所以，状态整个动态规划中第一点最难的部分。
动态规划要素
最优子结构：问题的最优解包含子问题最优解。即为：局部最优解 = 全局最优解（贪心在一些时间不符合此要求，因此 DP 题大多无法套用贪心）。
无后效性：
- 在推导后面状态时，仅考虑前面状态数值，不考虑是如何推导出来的。
- 某状态确定后，不会因为后面的决策而改变前面的赋值。
重叠子问题：不同的决策到达相同的状态时可能产生重复的状态，为了避免不必要的计算，我们通常使用记忆化搜索（在计算出新状态时将它存储起来一遍下次使用）来解决，这也是最经典的空间换时间。
状态转移方程
状态转移方程，就是如何将子问题转移至上级问题的公式。
在简单 DP 中，转移方程可以直接套用至 dfs, bfs 等爆搜算法。
DP 第二个难的部分就是列出状态转移方程。
例：设 为数列第 为的数，斐波那契数列的状态转移方程为 。
DP 如下：
1
2
3
4
5
| f[1] = 1;
f[2] = 1;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
cout << f[n];
|
同样的，我们可以将转移方程套用在递归上：
1
2
3
4
5
6
| int f(int n)
{
if (n == 1 || n == 2)
return 1;
return f(n - 1) + f(n - 2);
}
|
例题
例题 1
点我查看题目
20PTS
dfs。
注：两种情况
拿本物品
不拿本物品
1
2
3
4
5
6
7
8
9
| ll dfs(int i, int now, ll cnt)
{
if (i == n + 1)
return cnt;
if (!((now + 1) % 3) && ((now + 1) >= 3))
return max(dfs(i + 1, now + 1, cnt + (a[i] * 3)), dfs(i + 1, now, cnt));
else
return max(dfs(i + 1, now + 1, cnt + a[i]), dfs(i + 1, now, cnt));
}
|
AC
我们看题面，第一个思路看出的状态为： 表示前 个物品获得的最大奖金。
但是，我们发现不满足无后效性。
根据上述方法，我们尝试使用空间的代价来优化。
将状态改为： 表示前 个物品，当前物品数取余 为 时获得的最大奖金。
完整代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll a[100005];
ll f[100005][3];
ll ans;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][1];
f[i][2] = f[i - 1][2];
if (i >= 3)
f[i][0] = max(f[i][0], f[i - 1][2] + (a[i] * 3));
f[i][1] = max(f[i][1], f[i - 1][0] + a[i]);
if (i >= 2)
f[i][2] = max(f[i][2], f[i - 1][1] + a[i]);
ans = max(ans, f[i][0]);
ans = max(ans, f[i][1]);
ans = max(ans, f[i][2]);
}
cout << ans << "\n";
return 0;
}
|
例题二
点我查看题目
例题二前言：分类讨论
分类讨论就是将问题通过不同的结果 / 形式 / 不同点分成几类逐个解决。
例题二思路
既然说到分类讨论我们先来分个类。
最大最小怎么使用 求？使用最大 / 最小子段和模板求解即可。
最后对比一下就好了。
完整 Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll c;
ll a[100005];
ll solve()
{
ll original_sum = 0;
for (int i = 1; i <= n; ++i)
original_sum += a[i];
ll dp_max[100005], dp_min[100005];
dp_max[1] = a[1];
dp_min[1] = a[1];
ll maxx = dp_max[1];
ll minn = dp_min[1];
for (int i = 2; i <= n; i++)
{
dp_max[i] = max(a[i], dp_max[i - 1] + a[i]);
dp_min[i] = min(a[i], dp_min[i - 1] + a[i]);
maxx = max(maxx, dp_max[i]);
minn = min(minn, dp_min[i]);
}
ll res = max((c - 1) * maxx, (c - 1) * minn);
ll ans = original_sum + res;
return ans;
}
int main()
{
cin >> n >> c;
for (int i = 1; i <= n; ++i)
cin >> a[i];
cout << solve() << endl;
return 0;
}
|
后记
遇到学术性问题及错别字欢迎讨论！
参考资料
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
五大基本算法之动态规划算法 DP dynamic programming
动态规划解题套路框架 | labuladong 的算法笔记
1.最优子结构 | 数据结构与算法之美
