★动态规划（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<=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]

---

20230504 Update.

在隐隐约约或者分析出当前做的题目是dp题目的时候，dp题目的做法可以采取以下两种方式。

第一种：

1. 分析题目，提取关键。

2. 用数学语言表达问题。

3. 定状态转移方程。

4. 初始化。

5. 循环求解。

第二种：

1. 直接分析答案可能和哪些属性有关联。

2. 定状态转移方程。

3. 初始化。

4. 循环求解。

如果能用第一种分析出来那肯定是最好的，有了数学公式干什么都方便。

看例题。

[NOIP2012 普及组] 摆花 - 洛谷

因为本蒟蒻是蒟蒻（叉腰），所以直接用第二种方法。

可以发现摆花方案只和下面几种属性有关：
1. 花的种类

2. 花的数量，以及总数要小于一个限定数 -> 花的总数

3. 花的顺序

尝试做出定义  为用上前  种花，且到当前为止已经用了  盆花的所有方案数。

当我们正序迭代这个式子的时候，可以发现 3. 花的顺序 这个属性被隐含解决了。

即这个定义目前看来还是可行的。

根据定义易得：，其中  （不管他到现在最多能用多少，直接暴力枚举）。

初始化则为一种花都不用，一盆花都没有，即  。其中  。

出现了  所以循环的时候要注意下标越界，判断  。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e6+7,N=101;

int n,m,f[N][N],a[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];

    for(int i=0;i<=n;++i)
        f[i][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            for(int k=j-a[i];k<=j;++k)
                if(k>=0)f[i][j]=(f[i][j]+f[i-1][k])%MOD;
    cout<<f[n][m];
    return 0;
}

例题：[NOIP2008 普及组] 传球游戏 - 洛谷