★动态规划(DP算法)详解

这篇具有很好参考价值的文章主要介绍了★动态规划(DP算法)详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

★动态规划(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算法的入门问题之一

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

★动态规划(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 普及组] 采药 - 洛谷

★动态规划(DP算法)详解

★动态规划(DP算法)详解

这道题输入这么少也不用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状态,但是此处舍去了一维之后就会导致两者状态都会出现在这个小小的一维数组里面。

★动态规划(DP算法)详解

比如说用线段来表示所有情况,蓝色的得出了红色的状态。

但是如果我只剩下了一条线段呢?

★动态规划(DP算法)详解

 如果中间被前面先修改了,那么后面要更新状态的时候用的就是红色,而不是我们所需要的蓝色。

所以只能从后往前去推状态才能保证我们所需要的一直是蓝色,而不会被更新成红色。


发现了吧,重点在于找出继承状态(递推式),比如定义的是前n个人,而不是任意n个人,这样n-1和n的区别就在于多了一个人,只要让先前状态抽出能满足多一个人的情况,那就是后者的状态。

例题:5 倍经验日 - 洛谷

★动态规划(DP算法)详解

★动态规划(DP算法)详解

 和上面那道题基本没有什么区别,定义所有相关的基础态

定义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算法)详解

这道题每个药都可以无限采,也就是说同一行之间也要去迭代所有情况

★动态规划(DP算法)详解

上上题里面发现了,一维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 普及组] 摆花 - 洛谷

★动态规划(DP算法)详解

因为本蒟蒻是蒟蒻(叉腰),所以直接用第二种方法。

可以发现摆花方案只和下面几种属性有关:
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 普及组] 传球游戏 - 洛谷文章来源地址https://www.toymoban.com/news/detail-439294.html

到了这里,关于★动态规划(DP算法)详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划-简单了解下什么是期望DP

    首先说明下为啥是简单了解下,因为对于期望DP的问题 ,相较于一般的动态规划问题,可以说期望DP的题目相对较少,并且往往具有一定的难度。这是因为期望DP在解决问题时需要考虑状态的期望值,涉及到概率和随机性的计算,因此可能需要运用更多的数学知识和技巧 ,所

    2024年02月22日
    浏览(35)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(46)
  • 【算法】动态规划(dp问题),持续更新

    介绍本篇之前,我想先用人话叙述一般解决动态规划问题的思路: 动态规划的问题,本身有许多产生结果的可能,需要在具体题目下得到满足某个条件的解。 如何得到呢? 我们就需要根据这个具体问题,建立一个状态表( dp 表 ),在这张 dp 表中的每一个位置的数据都有明

    2024年02月04日
    浏览(48)
  • 算法——动态规划(DP,Dynamic Programming)

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年02月02日
    浏览(50)
  • 算法套路十三——动态规划DP入门

    动态规划和递归都是通过将大问题分解为较小的子问题来解决问题。它们都可以用来解决具有重叠子问题和最优子结构特性的问题。 递归是一种自顶向下的方法, 它从原始问题开始 ,递归地将问题分解为较小的子问题dfs(i)—— dfs(i)代表的是从第i个状态开始进行递归求解能

    2024年02月15日
    浏览(56)
  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(49)
  • Day36算法记录|动态规划 dp02

    步骤回顾: C语言版本写的很清楚 对应得Java版本视频解析 方法一: 动态规划 1 确定dp数组(dp table)以及下标的含义 dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。 2 . 确定递推公式 ,求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。 3. dp数

    2024年02月12日
    浏览(49)
  • 动态规划算法刷题笔记【状压dp】

    a1 == 1 判断是否为奇数,如果为1,则为奇数 因为奇数二进制末位一定是1,所以 与1 得到的结果是1 这里,114——2 14 ——第15位是1,可以表示14个1 i(1j)—— 从0开始是因为,原本第1位就是1。所以j=0时,对应的就是 i 的最低位 F l o y d Floyd Fl oy d 算法: n o w ∣ f l a g = = f l

    2024年02月11日
    浏览(41)
  • C++算法 —— 动态规划(7)两个数组的dp

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅读

    2024年02月07日
    浏览(52)
  • 动态规划dp详解(破解之道,就在其中)

    一.什么是动态规划 定义: 动态规划(英语:Dynamic programming,简称 DP),是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把 原问题分解为相对简单的子问题的方式 求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题

    2024年03月27日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包