动态规划（dp算法）详解-ag真人游戏

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

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

问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 
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<

    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]);

定义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];
如果能打过,那么我可以选择打或者不打
如果打不过,那只能不打

    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];

#include 
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<

很明显这道题i和i-1也是滚动使用的
不过n的范围不是很大,所以不考虑优化

#include 
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[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]