菜鸟笔记什么是动态规划：动态规划_百度百科
内容太多了不作介绍，重点部分是无后效性，重叠子问题，最优子结构。
问S->P1和S->P2有多少种路径数，毫无疑问可以先从S开始深搜两次，S->P1和S->P2找出所有路径数，但是当这个图足够大，那就会超时。
动态规划旨在用空间换时间，我们可以发现S->P2的路上，实际上重复计算了S->P1，然后再去计算P1->P2，如果我们第一次计算S->P1的时候，保留了P1点的路径数，那么就不用再次计算S->P1了。
无后效性：未来的状态不会影响过去的状态，如果我在P1->P2的时候，S->P1多了一条路出来，那么先前保留的路径数就是错误的。
经典的数塔问题也是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<=m;++i)
cin>>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 <bits/stdc++.h>
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<=m;++i)
cin>>t[i]>>v[i];
for(int i=1;i<=m;++i){
for(int j=1;j<=T;++j){
if(j>=t[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[m][T];
return 0;
}这道题还可以接着优化,因为不难发现dp[][]的一维空间始终是在dp[i]和dp[i-1]范围内
也就是说我们其实可以舍弃这一维来节约很大范围的空间。
dp代码
for(int i=1;i<=m;++i)
for(int j=T;j>=t[i];j--)
dp[j]=max(dp[j-t[i]]+v[i],dp[j]);内部循环必须从大到小，因为先前是应用了i-1先前状态去得出i状态，但是此处舍去了一维之后就会导致两者状态都会出现在这个小小的一维数组里面。
比如说用线段来表示所有情况，蓝色的得出了红色的状态。
但是如果我只剩下了一条线段呢？
如果中间被前面先修改了，那么后面要更新状态的时候用的就是红色，而不是我们所需要的蓝色。
所以只能从后往前去推状态才能保证我们所需要的一直是蓝色，而不会被更新成红色。
发现了吧，重点在于找出继承状态（递推式），比如定义的是前n个人，而不是任意n个人，这样n-1和n的区别就在于多了一个人，只要让先前状态抽出能满足多一个人的情况，那就是后者的状态。
例题：5 倍经验日 - 洛谷
和上面那道题基本没有什么区别，定义所有相关的基础态
定义dp[i][j]为前i个人 用j个药 可以获得的最大经验值然后就可以得出递推式
for(int i=1;i<=n;++i)
for(int j=1;j<=x;++j)
if(j>=use[i])
dp[i][j]=max(dp[i-1][j]+lose[i],dp[i-1][j-use[i]]+win[i]);
else
dp[i][j]=dp[i-1][j]+lose[i];
如果能打过,那么我可以选择打或者不打
如果打不过,那只能不打但是这道题有一个注意点是，J可以从0开始，因为存在不用药就可以打过的情况，所以先初始化不用药的情况。
初始化
for(int i=1;i<=n;++i)
if(use[i]==0)
dp[i][0]=dp[i-1][0]+win[i];
else
dp[i][0]=dp[i-1][0]+lose[i];AC代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e3+1;
long long n,x,win[MAXN],lose[MAXN],use[MAXN],dp[MAXN][MAXN];
//dp[i][j]前i个人,使用j个药,能获得的最大经验值
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>x;
for(int i=1;i<=n;++i){
cin>>lose[i]>>win[i]>>use[i];
}
for(int i=1;i<=n;++i)
if(use[i]==0)
dp[i][0]=dp[i-1][0]+win[i];
else
dp[i][0]=dp[i-1][0]+lose[i];
for(int i=1;i<=n;++i)
for(int j=1;j<=x;++j)
if(j>=use[i])
dp[i][j]=max(dp[i-1][j]+lose[i],dp[i-1][j-use[i]]+win[i]);
else
dp[i][j]=dp[i-1][j]+lose[i];
cout<<dp[n][x]*5;
return 0;
}很明显这道题i和i-1也是滚动使用的
不过n的范围不是很大,所以不考虑优化例题：疯狂的采药 - 洛谷
和上上题采药的区别就是，每个药可以无限采
每条线的含义都是一样的，也就是每个药都只能采一次。
这道题每个药都可以无限采，也就是说同一行之间也要去迭代所有情况
上上题里面发现了，一维dp一定要逆序时间才能得出不迭代自己的状态，那么这道题正序迭代即可。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int MAXM=1e4+1;
const int MAXT=1e7+1;
int T,m,t[MAXM],v[MAXM];
long long dp[MAXT];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>T>>m;
for(int i=1;i<=m;++i){
cin>>t[i]>>v[i];
}
for(int i=1;i<=m;++i){
for(int j=t[i];j<=T;++j){
dp[j]= max(dp[j],dp[j-t[i]]+v[i]);
}
}
cout<<dp[T];
return 0;
}j一定要从t[i]开始，不然下标要越界了。
如果要写出二维dp首先要改变定义，因为一个是只能用一次，一个是无限用，递推式必然不一样
定义dp[i][j]为采前i朵（无限采），消耗时间j内的最大价值
不难得出以下两种情况
1.当前时间可以采走这支草药
(1)继承先前状态
(2)迭代自己
综上dp[i][j]=max(dp[i-1][j],dp[i][j-t[i]]+v[i]);
注意此处是i,不是i-1
2.当前时间不够采走这支草药,采不了那就不采,继承先前状态.
即dp[i][j]=d[i-1][j]动态规划的难点不在于告诉你这道题是dp，让你分析如何写出递推式（这是很简单的，定义所有基础属性即可，通常也可以由解空间树转换得来，即由记忆化搜索转变为递推式）
而是在于如何分析出这道题是dp，比如把2022拆分成不同质数之和，质数最多可以有几个。
如果能想到2022是一个背包，里面放的素数是容量大小，抽象成01背包问题，那问题就会变的非常简单。
这点完全考验的是一个人的思维深度和广度，所以本蒟蒻不行（逃）