DP 详解

大家好，欢迎来到IT知识分享网。

更新日志

至管理：谢谢管理大大重复审核！

upd: 2/11/2024

更正第一，第二段的少数错别字。

感谢：

litjohn

DP 概述

DP 问题在 OIer 中很受欢迎，因为每个 DP 问题在某种意义上都是原创的，你必须努力思考其状态和状态转移方程才能为其发明解决方案。由于动态规划如此受欢迎，它可能是算法竞赛中最重要的掌握方法。

DP（Dynamic programming，全称动态规划），是一种基于分治，将原问题分解为简单子问题求解复杂问题的方法。

动态规划的耗时往往远少于朴素（爆搜）解法。

动态规划 and 递归

DP 可以被描述为一种通常基于问题的起始状态，以及连续状态之间的递归公式或关系的问题解决算法。

之前说过，动态规划也是分治思路，而递归更是传统的分治思路，而 DP 又是基于递归式求解的，但时间复杂度却大相径庭，为什么呢？

动态规划是 自底向上 思想，而递归是 自顶向下 解法。

自底向上 and 自顶向下？

自底向上

意思很简单，从下往上推导：$f(1)\to f(2)\to \cdots \to f(n-1)\to f(n)$。

这也是为什么 动态规划算法 脱离了 递归 的函数，改用循环迭代推到的原因。

自顶向下

反过来，自顶向下就是从上往下推，触底后在将结果返回回来。

$f(n)\to f(n-1)\to \cdots \to f(2)\to f(1)\to f(2)\to f(3)\to \cdots \to f(n-1)\to f(n)$

这也是为什么递归比动态规划时间复杂度高的多的原因。

我们可以看出，动态规划更像是递推算法的 plus 版。

状态的定义

前言：空间换时间

很简单的名字，即为使用空间的代价来确保不会超时。

状态？

状态，通俗来讲就是你 $f_{xxx}$ 代表的是什么。比如斐波那契数列中 $f_i$ 代表的就是第 $i$ 为是什么。

对于状态：

1. 状态越多，表示的信息越多，空间越大。
2. 反之，状态越少，表示的信息越少，空间越小。

在我们状态定义时，可能有这些情况：

$部分情况\{\begin{array}{l}状态太少？\{\begin{array}{ll}信息量太少& 无解\\ 信息量太少& 不满足动态规划要素\end{array}\\ 状态太多？\{\begin{array}{ll}空间太大& MLE\\ 需要太多时间更新状态& TLE\end{array}\end{array}$

所以，状态 and 状态转移方程时整个动态规划中最最最难的部分，想清楚这两点，这题也就解出来了。

动态规划要素

1. 最优子结构：问题的最优解 包含 子问题最优解。即为：局部最优解 = 全局最优解。
2. 无后效性：
   • 在推导后面状态时，仅在意前面状态数值，不在意是如何推导出来的。
   • 某状态确定后，不会因为后面的决策而改变前面的决策。
3. 重叠子问题：不同的决策到达相同的状态时可能产生重复的状态，为了避免不必要的计算，我们通常使用 记忆化搜索（在计算出新状态时将它存储起来一遍下次使用）来解决，这也是最经典的 空间换时间。

不满足这三点你还想 DP？想 peach 呢？

状态转移方程

状态转移方程，就是如何将子问题转移至父亲问题的公式。

在简单 DP 中，转移方程可以直接套用至 dfs, bfs 等爆搜算法。

DP 最难的部分就是列出状态转移方程，如果没有状态转移方程，一切都白搭。

例：设 $f_i$ 为数列第 $i$ 为的数，斐波那契数列的状态转移方程为 $f_i=f_{i-1}+f_{i-2}$。

DP 如下：

f[1] = 1; f[2] = 1; for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; // 转移方程 cout << f[n]; 

同样的，我们可以将转移方程套用在递归暴力上：

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.最优子结构 | 数据结构与算法之美

例题

例题 1

纯 DP

点我查看题目

20PTS

没看数据：好一个 dfs！

注：两种情况

1. 拿本物品
   • 3 倍奖金？
   • 1 倍奖金？
2. 不拿本物品

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

我们看题面，一眼看出的状态为：$f_i$ 表示前 $i$ 个物品获得的最大奖金。

但是，我们发现不满足无后效性。

根据上述方法，我们尝试使用空间的代价来优化。

将状态改为：$f_{i,j}$ 表示前 $i$ 个物品，当前物品数取余 $3$ 为 $j$ 时获得的最大奖金。

$fi,j=\{\begin{array}{l}j=0\{\begin{array}{ll}i\ge 3\{\begin{array}{ll}{f}_{i-1,0}& 不拿\\ f_{i-1,2}+a_i\times 3& 拿\end{array}& \\ f_{i-1,0}& 没有到3个，不存在这种情况。\end{array}\\ j=1\{\begin{array}{ll}{f}_{i-1,1}& 不拿\\ f_{i-1,0}+a[i]& 拿\end{array}\\ j=2\{\begin{array}{ll}i\ge 2\{\begin{array}{ll}{f}_{i-1,2}& 不拿\\ f_{i-1,1}+a_i& 拿\end{array}& \\ f_{i-1,2}& 没有至少2个物品，没有这种情况。\end{array}\end{array}$

完整代码为：

#include <bits/stdc++.h> using namespace std; #define ll long long int n; ll a[]; /* 20PTS 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)); } */ ll f[][3]; ll ans; int main() { 
    cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; // cout << dfs(1, 0, 0) << "\n"; 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; } 

例题二

点我查看题目

首先，我们欣赏一下原出题人的提示。

例题二前言：分类讨论

在看了许多不当人的讲解后，我浓缩出：分类讨论就是分类 –> 讨论！ 分类讨论就是将问题通过不同的结果 / 形式 / 不同点分成几类逐个解决。

例题二思路

既然说到分类讨论我们先来分个类。

$\max ({\sum }_{i=1}^N{A}_i)=\{\begin{array}{ll}C>0& \max ({\sum }_{i=L}^R{A}_i)\times C\\ C<0& \min ({\sum }_{i=L}^R{A}_i)\times C\end{array}$

最大最小怎么使用 $O(N)$ 求？Bingo！最大 / 最小 子段和即可。

最后比一下就好了。

完整 Code：

#include <bits/stdc++.h>  using namespace std; #define ll long long int n; ll c; ll a[]; ll solve() { 
    ll original_sum = 0; for (int i = 1; i <= n; ++i) original_sum += a[i]; ll dp_max[], dp_min[]; 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; }