DP 概述
DP 问题在 OIer 中很受欢迎，因为每个 DP 问题在某种意义上都是原创的，你必须努力思考其状态和状态转移方程才能为其发明解决方案。由于动态规划如此受欢迎，它可能是算法竞赛中最重要的掌握方法。
DP（Dynamic programming，全称动态规划），是一种基于分治，将原问题分解为简单子问题求解复杂问题的方法。
动态规划的耗时往往远少于朴素（爆搜）解法。
动态规划 and 递归
DP 可以被描述为一种通常基于问题的起始状态，以及连续状态之间的递归公式或关系的问题解决算法。
之前说过，动态规划也是分治思路，而递归更是传统的分治思路，而 DP 又是基于递归式求解的，但时间复杂度却大相径庭，为什么呢？
动态规划是 自底向上 思想，而递归是 自顶向下 解法。
自底向上 and 自顶向下？
自底向上
意思很简单，从下往上推导：。
这也是为什么 动态规划算法 脱离了 递归 的函数，改用循环迭代推到的原因。
自顶向下
反过来，自顶向下就是从上往下推，触底后在将结果返回回来。
这也是为什么递归比动态规划时间复杂度高的多的原因。
我们可以看出，动态规划更像是递推算法的 plus 版。
状态的定义
前言：空间换时间
很简单的名字，即为使用空间的代价来确保不会超时。
状态？
状态，通俗来讲就是你 代表的是什么。比如斐波那契数列中 代表的就是第 为是什么。
对于状态：
状态越多，表示的信息越多，空间越大。
反之，状态越少，表示的信息越少，空间越小。
在我们状态定义时，可能有这些情况：
所以，状态 and 状态转移方程时整个动态规划中最最最难的部分，想清楚这两点，这题也就解出来了。
动态规划要素
最优子结构：问题的最优解 包含 子问题最优解。即为：局部最优解 = 全局最优解。
无后效性：
重叠子问题：不同的决策到达相同的状态时可能产生重复的状态，为了避免不必要的计算，我们通常使用 记忆化搜索（在计算出新状态时将它存储起来一遍下次使用）来解决，这也是最经典的 空间换时间。
不满足这三点你还想 DP？想 peach 呢？
状态转移方程
状态转移方程，就是如何将子问题转移至父亲问题的公式。
在简单 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);
}
|
参考资料
Everything About DP
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
五大基本算法之动态规划算法 DP dynamic programming
动态规划解题套路框架 | labuladong 的算法笔记
1.最优子结构 | 数据结构与算法之美
例题
例题一思路
纯 DP
点我查看题目
没看数据：好一个 dfs！
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));
}
|
我们看题面，一眼看出的状态为： 表示前 个物品获得的最大奖金。
但是，我们发现不满足无后效性。
根据上述方法，我们尝试使用空间的代价来优化。
将状态改为： 表示前 个物品，当前物品数取余 为 时获得的最大奖金。
完整代码为：
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;
}
|
点我查看题目
首先，我们欣赏一下原出题人的提示。
例题二前言：分类讨论
在看了许多不当人的讲解后，我浓缩出：分类讨论就是分类 –> 讨论！分类讨论就是将问题通过不同的结果 / 形式 / 不同点分成几类逐个解决。
例题二思路
既然说到分类讨论我们先来分个类。
最大最小怎么使用 求？Bingo！最大 / 最小 子段和即可。
最后比一下就好了。
完整 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;
}
|
