★动态规划（DP算法）详解

什么���动态规划：动态规划_百度百科

内容太多了不作介绍，重点部分是无后效性，重叠子问题，最优子结构。

问S->P1和S->P2有多少种路径数，毫无疑问可以先从S开始深搜两次，S->P1和S->P2找出所有路径数，但是当这个图足够大，那就会超时。

动态规划旨在用空间换时间，我们可以发现S->P2的路上，实际上重复计算了S->P1，然后再去计算P1->P2，如果我们第一次计算S->P1的时候，保留了P1点的路径数，那么就不用再次计算S->P1了。

无后效性：未来的状态不会影响过去的状态，如果我在P1->P2的时候，S->P1多了一条路出来，那么先前保留的路径数就是错误的。

tip：下面的例题讲解并不是特别好，还未修正，建议先拉到最下面看20230504 Update.

---

经典的数塔问题也是dp算法的入门问题之一

假设你有这么一个数塔，你的目标是求最底层到最高层，求出最大路径和

比如3->7->2->9这个路径，他的路径和是3+7+2+9

不难发现如果要求到9的最大路径和，首先要求出他前一层的最大路径

核心代码dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+a[i][j]

dp[i][j]（9的最大路径和)

a[i][j]（9自己）

dp[i-1][j]（前一层5的最大路径和）dp[i-1][j+1]（前一层2的最大路径和）

在前一层的最大路径和取大的那一个

---

例题：[NOIP2005 普及组] 采药 - 洛谷

这道题输入这么少也不用scanf了，直接上cin加上小优化

inline void scan(){    ios::sync_with_stdio(false);//解除与scanf和cout的同步,具体体现在缓冲区    cin.tie(nullptr),cout.tie(nullptr);//可以加快一点速度    cin>>T>>m;    for(int i=1;i>t[i]>>v[i];}

很明显就是各个最优子问题的问题，要取到最多的价值，必然前一个状态也是最多的。

所以考虑定义问题的全部基础属性，每个草药有价值和对应所需的时间，目标是最大价值。

作出以下定义

定义dp[i][j]为采前i朵，消耗时间j内的最大价值    不难得出以下两种情况1.当前时间可以采走这支草药  (1)如果要采这支采药,那先前状态就要预留j-t[i]时间来满足定义  (2)如果不采那最大价值就是先前状态dp[i-1][j]  因为不清楚哪一种情况更好,但是我们只需要最大值,所以max  综上dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);2.当前时间不够采走这支草药,采不了那就不采,继承先前状态.    即dp[i][j]=d[i-1][j]或者说延续用上文的想法,n支草药价值最大我不知道如果只有1支草药呢?,那我是不是就知道了1支草药知道了,那我2支草药是不是也知道了

然后...直接从基础状态循环到结束，即从第一支草药开始循环。

显而易见不能从采最后几朵开始往前判断，前面状态都不清楚，怎么可以从后面开始。

AC代码

#include using namespace std;int T,m,t[101],v[101],dp[101][1001];int main(){    ios::sync_with_stdio(false);    cin.tie(nullptr),cout.tie(nullptr);    cin>>T>>m;    for(int i=1;i>t[i]>>v[i];    for(int i=1;ilose[i]>>win[i]>>use[i];    }    for(int i=1;im;    for(int i=1;i>t[i]>>v[i];    }    for(int i=1;in>>m;    for(int i=1;i>a[i];    for(int i=0;i