第四十六章 动态规划——状态机模型

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

一、通俗理解状态机DP

其实状态机DP只是听起来高级,其实我们之前做的所有关于DP的题几乎都算是状态机,为什么呢?

1、什么是状态机

大家继续向下看:

DP解决的是多决策的问题,那么我们可以把01背包问题画成下面的图:
状态机模型,算法合集(c++实现),动态规划,算法按照正常的逻辑,我们一般都是从第一个物品开始看,决定选或者不选,然后再去看第二个物品。那么我们现在只看其中一个物品,这个物品无非就两个状态,在背包里,不在背包里。

其实这两个状态就构成了一个状态机。
状态机模型,算法合集(c++实现),动态规划,算法

写到这里,我们就可以通俗地理解一下状态机,状态机的作用就是记录一个事件所有可能的存在状态以及这些状态之间的联系。这个作用或许大家现在还会感到一些模糊,但是没关系,后面的例题中作者会进行详细地讲解,让大家深刻体会到。

2、什么是状态机DP

那么什么是状态机DP呢?这种DP方式和之前的DP有什么不同呢?

状态机DP就是在DP数组中专门开辟一个维度记录当前事件所处的状态,比如背包问题如果写成状态机DP的模式,我们会写成 f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]或者 f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0],此时的1代表第i个物品在背包里,0说明第i个物品不在背包里。状态定义可以写作:在前i个物品中选,背包容量为j,且第i个物品在(或者不在)背包中的时候,我们所能携带的最大价值。

其实通过这个例子,大家就能明显地感觉到,在状态机模型中我们强调并记录当前事物的状态

可是这样做有啥用呢?

作者可以给01背包问题加上一个情景,不能选择相邻的物品。此时如果还按照我们之前的做法,用f[i][j]来定义的话,你对某个物品的具体状态是模糊的。我们一般是用f[i-1][j]和f[i-1][j-v]+w来写转移方程,但是你无法判断第i-1个物品是否在背包里,也就是说你不知道第i-1个物品所处的状态。

但是此时如果按照状态机模型来写,特意强调一下某个物品的状态,我们就可以利用第三维度的0和1来判断能否选当前的物品。

那么此时可以总结一下什么时候用状态机DP,当某个事件的状态影响到后面事件的决策的时候,我们需要在状态定义的时候记录事件状态,即状态机DP。

二、例题

1、AcWing 1049. 大盗阿福

(1)问题

状态机模型,算法合集(c++实现),动态规划,算法

(2)分析

这道题其实就算是一个01背包问题加状态机DP,如果转化为01背包问题的话,即:从1到i个物品里面选,不限制背包容量但是不能够选择相邻物品的情况下,所能携带的最大价值。

a.状态定义

按照刚刚的状态机的解释来看,这道题中把某个店铺看作一个事件,那么抢或者不抢就是这个店铺的状态。而状态机往往也记录了一个事件中各个状态的转移。

但是这里为了解释的更加清楚,我们找到两个相邻的店铺,分别表示出他们的状态,画出状态之间的转移:如下图所示
状态机模型,算法合集(c++实现),动态规划,算法
由于题目中强调不能抢相邻的,所以如果我们抢了店铺A,那么下一次就不能抢店铺B,(假设A和B相邻)。

所以我们的f[i][j]表示的是,在前i个店铺里抢劫,且抢(或者不抢)店铺i的情况下,所能抢得的最大价值。0表示不抢,1表示抢。

b.状态转移

上面这个图其实也说明了状态转移方程的书写思路。这里就直接写了。
f ( i , 1 ) = f ( i − 1 , 0 ) + w [ i ] f ( i , 0 ) = m a x ( f ( i − 1 , 1 ) , f ( i − 1 , 0 ) ) f(i,1)=f(i-1,0)+w[i]\\ f(i,0)=max(f(i-1,1),f(i-1,0)) f(i,1)=f(i1,0)+w[i]f(i,0)=max(f(i1,1),f(i1,0))
最后在f(n,1)和f(n,0)中选一个最大值。

c.循环设计

根据转移方程,我们写一个一维的循环即可。

d.初末状态

根据转移方程,我们需要初始化的是两个状态:f[0][0]和f[0][1]。很明显第0个店铺是不存在的,所以f[0][1]是不合法的,初始化为负无穷即可。或者从另一个角度理解,我们的第1个店铺可选可不选,所以第0个店铺一定是不能选的,那么为了不选第0个,只能将f[0][1]变成负无穷。
其实这里不管它也能过,因为店铺的价值最少就是0,虽然这个状态不合法, 但是不影响答案。可是在后续的题目中,初始化会对答案造成一定影响,所以最好还是对不合法的状态进行一定的初始化。

(3)代码

#include<iostream>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int w[N],f[N][2];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)scanf("%d",w+i);
        f[0][0]=0,f[0][1]=-INF;
        for(int i=1;i<=n;i++)
        {
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            f[i][1]=f[i-1][0]+w[i];   
        }
        cout<<max(f[n][0],f[n][1])<<endl;
    }

    return 0;   
}

2、AcWing 1057. 股票买卖 IV

(1)问题

状态机模型,算法合集(c++实现),动态规划,算法

(2)分析

这道题我们首先得明确一点,我们只有一支股票,只是这支股票在不同天有着不同的价格,因此我们可以把天作为单位划分不同的状态。同时这道题中还有一个关键的信息,同一时刻,我们只能做一次交易,什么意思呢?即当这只股票在我们的手里的时候,我们无法再次进行购买,只能把这个股票卖出或者不卖。如果这支股票不在我们手里,那么我们只能选择买或者不买。

同时,题目还规定,买入股票和卖出股票算一次交易。因此,我们可以认为二者各算半次交易。由于只有手中有股票的时候才能卖出,说明再次之前已经买入。因此,我们可以在卖出股票的时候,把我们的交易次数+1。

a.状态定义

f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0]表示在1到i天中买卖股票,当前已经进行了j次交易,且在第i天里,手中没有当前股票的时候,所得到的最大利润。
f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]表示在1到i天中买卖股票,当前已经进行了j次交易,且在第i天里,手中有当前股票的时候,所得到的最大利润。

b.状态转移

状态转移的话,我们可以画出下面的图,这样更加清晰:
状态机模型,算法合集(c++实现),动态规划,算法

c.循环设计

这道股票的题其实如果不看状态之间的影响的话,其实就是一个01背包,因此我们按照01背包的逻辑来循环即可,即外层循环i,内层循环j。

d.初末状态

这里初始化比较麻烦,因为我们将卖出股票算作一次完整的交易,这一规定使得我们的初始化变得比较复杂。根据我们的规定,f[i][0][1]这种定义也是存在的,即从0到i中选一个最便宜的购入,就是当下的最优解。但是f[0][0][1]是不合法的,因此第0天的股票多贵不知道,没法买,而f[0][0][0]初始化为0即可,这个状态是存在的,第0天的股票虽然不存在,但是我们不买,依旧是0。

如果不想这么复杂的话,我们可以规定买入股票的时候,算一次完整的交易。此时我们发现f[i][0][1]是不合法的了。因为既然有股票,交易次数就不是0了。文章来源地址https://www.toymoban.com/news/detail-600918.html

(3)代码

规定卖出算一次交易
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10,k=110;
int f[N][k][2],w[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",w+i);
    memset(f,0xcf,sizeof f);
    f[0][0][0]=0;
    for(int i=1,minv = 1e6;i<=n;i++)
    {
        f[i][0][0]=0;
        minv=min(minv,w[i]);
        f[i][0][1]=-minv;
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j-1][1]+w[i]);
            f[i][j][1]=max(f[i-1][j][1],f[i-1][j][0]-w[i]);
        }
    }
    int res=0;
    for(int i=0;i<=m;i++)res=max(f[n][i][0],res); 
    cout<<res<<endl;
    return 0;
}
规定买入算一次交易
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10,k=110;
int f[N][k][2],w[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",w+i);
    memset(f,0xcf,sizeof f);
    for(int i=0;i<=n;i++)f[i][0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);
            f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);
        }
    }
    int res=0;
    for(int i=0;i<=m;i++)res=max(f[n][i][0],res); 
    cout<<res<<endl;
    return 0;
}

到了这里,关于第四十六章 动态规划——状态机模型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 代碼隨想錄算法訓練營|第四十六天|完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ。刷题心得(c++)

    目录 动态规划 - 完全背包 和01背包的差別 定義 核心代碼 遍歷順序 總結 讀題 518. 零钱兑换 II 自己看到题目的第一想法 看完代码随想录之后的想法 377. 组合总和 Ⅳ 自己看到题目的第一想法 518. 零钱兑换 II - 實作 思路 Code 377. 组合总和 Ⅳ - 實作 思路 Code 總結 自己实现过

    2024年02月08日
    浏览(40)
  • 第四十六节 Java 8 Stream

    Java 8 API添加了一个新的抽象称为流Stream,可以让你以一种声明的方式处理数据。 Stream 使用一种类似用 SQL 语句从数据库查询数据的直观方式来提供一种对 Java 集合运算和表达的高阶抽象。 Stream API可以极大提高Java程序员的生产力,让程序员写出高效率、干净、简洁的代码。

    2024年04月23日
    浏览(35)
  • 学习JAVA打卡第四十六天

    Date和Calendar类 Date类 ⑴使用无参数构造方法 使用Date 类的无参数构造方法创建的对象可以获取本机的当前日期和时间,例如: Date nowtime =new Date(); ⑵使用带参数的构造方法 计算机系统将其自身的时间的设“公元”设置在1970年1月1日零时可(格林威治时间),可以根据这个

    2024年02月11日
    浏览(45)
  • 【从零开始学习JAVA | 第四十六篇】处理请求参数

            在我们之前的学习中,我们已经基本学习完了JAVA的基础内容,从今天开始我们就逐渐进入到JAVA的时间,在这一大篇章,我们将对前后端有一个基本的认识,并要学习如何成为一名合格的后端工程师。今天我们介绍的内容是:如何在后端处理前端的请求 目录 前言:

    2024年02月11日
    浏览(40)
  • 60题学会动态规划系列:动态规划算法第四讲

    买卖股票相关的动态规划题目 文章目录 1. 买卖股票的最佳时机含冷冻期 2. 买卖股票的最佳时期含⼿续费 3. 买卖股票的最佳时机III 4. 买卖股票的最佳时机IV 力扣链接:力扣 给定一个整数数组 prices ,其中第    prices[i]  表示第  i  天的股票价格 。​ 设计一个算法计算出最

    2024年02月13日
    浏览(33)
  • order by之后的injection(sqllabs第四十六关)

    这一关的sql语句是利用的order by 根据输入的id不同数据排序不一样可以确定就是order by order by后面无法使用ubion注入(靠找不到) 可以利用后面的参数进行攻击 1)数字 没作用考虑布尔类型 rand和select ***都可以 或者利用and 或者报错注入(延时注入也是可以的) 2))procedure analys

    2024年02月03日
    浏览(29)
  • 小白到运维工程师自学之路 第四十六集 (mongodb复制集)

           1、 MongoDB复制集(MongoDB Replica Set)是MongoDB提供的一种高可用性和数据冗余的解决方案。它由多个MongoDB实例组成,其中一个作为主节点(Primary),其他节点则扮演从节点(Secondary)的角色。主节点处理所有的写操作和客户端请求,而从节点负责复制主节点的数据并

    2024年02月13日
    浏览(46)
  • C++算法之旅、06 基础篇 | 第四章 动态规划 详解

    状态表示 集合 满足一定条件的所有方案 属性 集合(所有方案)的某种属性(Max、Min、Count等) 状态计算(集合划分) 如何将当前集合划分成多个子集合 状态计算相当于集合的划分 :把当前集合划分成若干个子集,使得每个子集的状态可以先算出来,从而推导当前集合状态

    2024年02月09日
    浏览(35)
  • 【AI视野·今日NLP 自然语言处理论文速览 第四十六期】Tue, 3 Oct 2023

    AI视野 ·今日CS.NLP 自然语言处理论文速览 Tue, 3 Oct 2023 (showing first 100 of 110 entries) Totally 100 papers 👉 上期速览 ✈更多精彩请移步主页 It\\\'s MBR All the Way Down: Modern Generation Techniques Through the Lens of Minimum Bayes Risk Authors Amanda Bertsch, Alex Xie, Graham Neubig, Matthew R. Gormley 最小贝叶斯风险 M

    2024年02月08日
    浏览(49)
  • 【算法学习】简单多状态-动态规划

            本篇博客记录动态规划中的简单多状态问题。         在之前的动态规划类型的题中,我们每次分析的都只是一种或者某一类的状态,定义的dp表也是围绕着一种状态来的。         现在可能对于一种状态,存在几种不同的子状态,在状态转移过程中相互影响。此时

    2024年01月18日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包