动态规划（DP）（细致讲解+例题分析）_动态规划解题思路和讲解

动态规划（DP）

本章将介绍介绍动态规划（Dynamic Programming, DP）及其解决的问题、根据其设计的算法及优化。

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。

动态规划原理

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

最优子结构

具有最优子结构也可能是适合用贪心的方法求解。

注意要确保我们考察了最优解中用到的所有子问题。

1. 证明问题最优解的第一个组成部分是做出一个选择；
2. 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
3. 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
4. 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面：

1. 原问题的最优解中涉及多少个子问题；
2. 确定最优解使用哪些子问题时，需要考察多少种选择。

子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

无后效性

已经求解的子问题，不会再受到后续决策的影响。

子问题重叠

如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

1. 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
2. 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
3. 按顺序求解每一个阶段的问题。

如果用图论的思想理解，我们建立一个 有向无环图，每个状态对应图上一个节点，决策对应节点间的连边。这样问题就转变为了一个在 DAG 上寻找最长（短）路的问题（参见：DAG 上的 DP）。

1. [P1048 NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态

首先定义状态 $dp[i][j]$ 以 j 为容量为放入前i个物品(按 ii 从小到大的顺序)的最大价值，那么 i=1 的时候，放入的是物品 1 ，这时候肯定是最优的啦！

那考虑一下 j，j是当前容量，如果 j<5，那么是不是就不能放，$dp[1][j](j<5)=0$；那如果 j>5，就可以放了，$dp[1][j](j>=5)=20$；

接着 i=2 放两个物品，求的就是 $dp[2][j]$ 了，当 j<5 的时候，是不是同样的 $dp[2][j](j<5)$ 等于0；那当 j<6 是不是还是放不下第二个，只能放第一个；

那 j>6 呢？是不是就可以放第二个了呢？是可以，但是明显不是最优的，用脑子想了一下，发现 $dp[2][j](j>6)=20$，这个 20 怎么来的呢，当然是从前一个状态来的（注意这里就可以分为两种情况了）：一种是选择第二个物品放入，另一种还是选择前面的物品；

让我们假设一下 j=10吧，可能会比较好理解！这时候：

$dp[2][10]=max((dp[1][10-w[2]])+v[2],dp[1][10])$

$dp[2][10]=max(dp[1][4])+10,dp[1][10])$

#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#define endl \'\\n\'using namespace std;using ll = long long;int dp[1001][1010];int main(){vectorv1(1001);vectorv2(1001);int m, n;cin >> m >> n;for (int i = 1; i > v1[i] >> v2[i];}for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){if (v1[i] <= j){dp[i][j] = max(dp[i - 1][j], v2[i] + dp[i - 1][j - v1[i]]);}else{dp[i][j] = dp[i - 1][j];}}}cout << dp[n][m];return 0;}

#include

2. P1510 精卫填海 - 洛谷 | 计算机科学教育新生态

然后就该开始无尽的思索了 这题的状态转移方程是什么？

本蒟蒻的思路是将体力看做背包 将石子看做物品 然后就很自然地得出了本题的状态转移方程：

f[j]=max(f[j],f[j-w[i]]+v[i])

#includeusing namespace std;using ll = long long;vector f, w, v;int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int vn, n, c, sum = 0; cin >> vn >> n >> c; v.resize(n + 1); w.resize(n + 1); f.resize(c + 1, 0); for(int i = 1; i > v[i] >> w[i]; sum += v[i]; } if(sum < vn) { cout << \"Impossible\" << \'\\n\'; return 0; } for(int i = 1; i = w[i]; --j) f[