动规训练4

目录

一、买股票的最佳实际含冷冻期

1、题目解析

2、算法原理

a状态表示方程

b状态转移方程

c初始化

d填表顺序

e返回值

3、代码

4、感想

二、买股票的最佳时机函手续费

1、题目解析

2、算法原理

a状态表示方程

b状态转移方程

c初始化

d填表顺序

e返回值

3、代码

4、写题感悟

三、买卖股票最佳时机4

1、题目解析

2、算法原理

a状态表示方程

b状态转移方程

c初始化

d填表顺序

e返回值

3、代码


这篇文章每道题我都会以题目解析、算法原理、以及代码编写这三个模块进行讲解。

在算法原理这里,我们使用动态规划的解题模式进行讲解:

  1. 找出状态表示方程
  2. 找出状态转移方程
  3. 如何进行初始化
  4. dp表的填写顺序
  5. 该返回什么值

推荐从专题中的动态规划1开始进行训练,由浅入深

一、买股票的最佳实际含冷冻期

1、题目解析

这道题就是一个先买——>卖——>冷冻期——>买这三个过程然后期间可以选择何时卖也可以选择买,但是主体上就是按照这个流程来的。

而且通过示例二可以得出,只有一天交易的时候不要买入,不然会亏本

2、算法原理

a状态表示方程

经验+题目要求

dp[i]粗浅的表示当天结束后获得的最大利润

但是dp[i]会涵盖三种状态

  • 买入状态——手上已经买入了股票
  • 冷冻期状态——将股票卖出后进入的状态
  • 可交易状态——经过冷冻期可以选择对当天股票是否买入的状态

这三种情况我们需要分别讨论,就需要三个表来表示。

因此状态表示方程应该是:

dp[i][0]表示第i天结束后,处于已买入状态的最大利润。

dp[i][1]表示第i天结束后,处于可交易状态的最大利润。

dp[i][2]表示第i天结束后,处于冷冻期状态的最大利润。

b状态转移方程

根据最近的一步划分问题

这道题目复杂的地方在于,最近的一步也有三种情况,我们要分别讨论前一天的三种情况怎么转换成今天的三种情况之一。

以转换成买入这种状态我们就需要讨论三种情况,

然后另外拉警钟情况都需要分别讨论,但其实有些情况是不可能达成的,以上面为例:

  • 买入——>买入,啥事不做就可以达成了
  • 冷冻——>买入,不可能达成,前一天结束时冷冻期意味着今天就是冷冻期。
  • 可交易——>买入,前一天结束是可交易,那我今天买入股票,今天结束就是买入状态了。

所以最后只有这两种情况

讨论完:

所以状态转移方程为:

dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i])

dp[i][1]=max(dp[i-1][1],dp[i-1][2])

dp[i][2]=dp[i-1][0]+p[i]

c初始化

为了避免边界问题:

将dp[0][0],dp[0][1],dp[0][2]这三个值初始化,分别是:-p[i],0,0

d填表顺序

从左到右,每次每次填入上个表。

e返回值

返回最后一天三种情况最大值即可

3、代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //建表
        //初始化
        //填表
        //返回值
        int n=prices.size();
        int dp[n][3];
        dp[0][0]=0-prices[0];
        dp[0][1]=0;
        dp[0][2]=0;
        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
            dp[i][2]=dp[i-1][0]+prices[i];
        }
        return max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
    }
};

4、感想

写到这道题的时候我感觉动态规划的解题方法是将所有情况穷举完了,然后选取最合适的值,尽管我们知道有些地方可以优化,但是这种穷举的方法反而可以帮我们解决处理这些优化地方的思考。

就像是返回值,我们直觉上会觉得返回值那天肯定不需要购入股票了,我们压根就不需要考虑这情况。但是站在代码的层面上考虑的话,就是多加了一个比较的是,这样还不需要我们去考虑一些特殊情况。

在写一道题目时侯我们可以根据示例,将一道题准确的得出最优解,但是要我们总结其中逻辑时却无从下手,因为情况太多了,反正你是一步接着一步,我把每一步的情况考虑清楚的话是可以选出我们需要的结果的,这其实也是一种剪枝思想的实现。

二、买股票的最佳时机函手续费

1、题目解析

相较于第一道题,这里有三种状态——买入后、卖出后、可买入。不过在一个完整的交易过程后需要扣除一个手续费。

2、算法原理

a状态表示方程

经验+题目要求

dp[i]粗浅的表示第i天后获得的最大利润

不过第i天有可能有三种情况,买入后、卖出后、可买入

经过分析:

我们发现买入到达可买是没有任何数值变换的,所以其实这一种状态其实是没有 必要的。

简化成:

所以我们需要运营两个表:

dp[i][0]表示第i天结束后为未持有股票的情况下拥有的最高利润

dp[i][0]表示第i天结束后为持有股票的情况下拥有的最高利润 

b状态转移方程

通过最近的一步简化问题。

分析可以得出

dp[i][0]有可能是

要想让我这一个i的值最大化,当然是要选择i-1值的最大情况 

 dp[i][1]有可能是:

c初始化

为了避免边界问题,考虑dp[0][0],和dp[0][1]即可

dp[0][0]=0

dp[0][1]=0-p[i]

d填表顺序

从左到右,两个表同时填

e返回值

max(dp[n-1][0],dp[n-1][1])

3、代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        //建表
        //初始化
        //填表
        //返回值
        int n=prices.size();
        int dp[n][2];
        dp[0][0]=0;
        dp[0][1]=0-prices[0];
        for(int  i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
            dp[i][1]=max(dp[i-1][0]-prices[i],dp[i-1][1]);
        }
        return max(dp[n-1][0],dp[n-1][1]);
    }
};

4、写题感悟

这种选择的思路感觉有点像是比较大小时,每次保存一个最小值

int my_min=0;
for(auto e:arr)
{
    if(my_min>e)
        my_min=e;
}

这道题是每次当前状态下最优解,你有更好的办法再来代替我

三、买卖股票最佳时机4

1、题目解析

2、算法原理

a状态表示方程

经验+题目要求

dp[i]粗浅的表示第i天结束后获得的利润最高

但是在第i天结束后又两种情况,手上持有股票、手上未持有股票。我们用两张表来表示:

f[i]表示第i天后持有股票时的最高利润

g[i]表示第i天后未持有股票时的最高利润

又这道题有一个附加条件,只最多只能进行k次交易。我们还有一种特殊状态需要维护、考虑,而且这种状态是影响每一天获取过程的

所以我们通过一个二维数组表示这个状态转换方程

f[i][j]表示第i天后持有股票的情况剩余j次交易机会的最高利润

g[i][j]表示第i天后未持有股票剩余j次交易机会的最高利润

b状态转移方程

还是那个小技巧:通过前一步,划分问题

最近的一步就是前一天,

持有股票的状态需要前一天未持有股票的状态买入、或者前一天本身就持有股票

未持有股票的状态需要前一天持有股票的状态卖出、或者前一天本身就未持有股票

假设这个图是表示f[i][j]的,图中三角形的位置只会由上面和右上这两种情况得出。

由此可以得出状态转移方程:

f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i])

g[i][j]=max(g[i-1][j],g[i-1][j+1]+prices[i])

c初始化

初始化需要解决的问题就是边界问题。

由状态转移方程可以观察出,容易出现边界问题的下标为i-1,j+1这两个地方。

所以我们需要对第一行和最后一列特殊处理。

for(int i=0;i<=k;i++){//对第一行进行特殊处理
            f[0][i]=0-prices[0];
            g[0][i]=0;
        }

 持有股票就减去价格,未持有就i为0

有同学可能会疑惑,为什么f[0][0]也可以这样赋值,应为它影响不到后续的结果,这样还使代码更加简洁。

最后一列我们进过特殊情况处理即可,在填写表格时:

        for(int i=1;i<n;i++){
            for(int j=0;j<=k;j++){
                if(j==k){
                    f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
                    g[i][j]=g[i-1][j];
                    continue;
                }
                f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j]=max(f[i-1][j+1]+prices[i],g[i-1][j]);
            }
        }

d填表顺序

从左到右,同时填写两个表

e返回值

返回最后一天各个情况的最大值

        int Max=INT_MIN;
        for(int i=0;i<=k;i++){
            int tem;
            tem=max(f[n-1][i],g[n-1][i]);
            Max=max(tem,Max);
        }
        return Max;

3、代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        //建表
        //初始化
        //填表
        //返回值
        int n=prices.size();
        int f[n][k+1],g[n][k+1];
        f[0][0]=0;
        g[0][0]=0;
        for(int i=1;i<=k;i++){
            f[0][i]=0-prices[0];
            g[0][i]=0;
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<=k;j++){
                if(j==k){
                    f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
                    g[i][j]=g[i-1][j];
                    continue;
                }
                f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j]=max(f[i-1][j+1]+prices[i],g[i-1][j]);
            }
        }
        int Max=INT_MIN;
        for(int i=0;i<=k;i++){
            int tem;
            tem=max(f[n-1][i],g[n-1][i]);
            Max=max(tem,Max);
        }
        return Max;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521101.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

STM3定时器输入捕获、超声波测距

1、超声波测距模块介绍 1、HC-SR04共四个引脚&#xff1a;VCC、GND、Trig、Echo&#xff0c;如下图 2、使用 1、通过gpio口向Trig引脚发送一个脉冲信号。 2、HC-SR04接收到脉冲信号后&#xff0c;就会向外发送一段超声波&#xff0c;模块会将echo拉高。 …

Web CSS笔记3

一、边框弧度 使用它你就可以制作盒子边框圆角 border-radius&#xff1a;1个值四个圆角值相同2个值 第一个值为左上角与右下角&#xff0c;第二个值为右上角与左下角3个值第一个值为左上角, 第二个值为右上角和左下角&#xff0c;第三个值为右下角4个值 左上角&#xff0c;右…

舞蹈网站制作分享,舞蹈培训商城网站设计案例分享,wordpress主题分享

嘿&#xff0c;朋友们&#xff01;今天我要跟你们唠一唠一个超级酷炫的舞蹈培训商城网站设计案例。 咱先说说这个网站的目标哈&#xff0c;那就是得让喜欢舞蹈的小伙伴们能够轻轻松松找到自己心水的课程和商品。 那制作过程都有啥呢&#xff1f;别急&#xff0c;听我慢慢道来。…

c# wpf LiveCharts 绑定 多线条 简单试验

1.概要 c# wpf LiveCharts 绑定 多线条 简单试验 2.代码 <Window x:Class"WpfApp3.Window4"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http:…

清明假期作业

1、实现文件夹的拷贝功能 注意判断被拷贝的文件夹是否存在&#xff0c;如果不存在则提前 不考虑递归拷贝的问题 #include<myhead.h> int my_copy(char* name,const char *p) {char buf[256]"./";strcat(buf,p);strcat(buf,"/");strcat(buf,name);in…

P1001 A+B Problem

1.题目背景 强烈推荐新用户必读帖。 不熟悉算法竞赛的选手请看这里&#xff1a; 算法竞赛中要求的输出格式中&#xff0c;**不能有多余的内容&#xff0c;这也包括了“请输入整数a和b” 这一类的提示用户输入信息的内容。**若包含了这些内容&#xff0c;将会被认为是Wrong Answ…

嵌入式Qt QGridLayout网格布局管理器

一.QGridLayout网格布局管理器 //以行为单位 设置比例系数 void QGridLayout::setRowStretch ( int row, int stretch ) //以列为单位 设置比例系数 void QGridLayout::setColumnStretch ( int column, int stretch ) 实验&#xff1a; Widget.h&#xff1a; #ifndef _WIDGE…

dm8数据迁移工具DTS

dm8数据迁移工具DTS DTS工具介绍 DM数据迁移工具提供了主流大型数据库迁移到DM、DM到DM、文件迁移到DM以及DM迁移到文件的功能。DM数据迁移工具采用向导方式引导用户通过简单的步骤完成需要的操作。 DM数据迁移工具支持&#xff1a; ◆ 主流大型数据库Oracle、SQLServer、MyS…

3.6 CSS定位

CSS定位可以将HTML元素放置在页面上指定的任意地方。CSS定位的原理是把页面左上角的点定义为坐标为(0,0)的原点&#xff0c;然后以像素为单位将整个网页构建成一个坐标系统。其中x轴与数学坐标系方向相同&#xff0c;越往右数字越大&#xff1b;y轴与数学坐标系方向相反&#x…

r3live使用realsense避免相机内参标定

话题 /camera/color/camera_info 消息格式 sensor_msgs/CameraInfo distortion_model&#xff1a;指定了相机畸变模型&#xff0c;"plumb_bob"简单的径向和切向畸变模型 D&#xff1a;畸变参数&#xff0c;取决于畸变模型&#xff0c;(k1, k2, t1, t2, k3)&#xf…

Shell编程初识

Shell初识 ShellShell 脚本Shell 环境第一个shell脚本实例 运行 Shell 脚本方法&#xff1a;1、作为可执行程序2、作为解释器参数3.使用 . (空格)脚本名称来执行4.使用 source 来执行(主要用于生效配置文件)区别1.关于执行权限2.关于是否开启子shell线程 脚本排错及问题判断she…

dm8 备份与恢复

dm8 备份与恢复 基础环境 操作系统&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) 数据库版本&#xff1a;DM Database Server 64 V8 架构&#xff1a;单实例1 设置bak_path路径 --创建备份文件存放目录 su - dmdba mkdir -p /dm8/backup--修改dm.ini 文件…

Linux学习之路 -- 进程篇 -- PCB介绍2 -- 标识符和进程创建

前面我们介绍了的进程的标识符&#xff0c;下面继续介绍进程标识符和进程创建的知识。 目录 一、进程创建 <1>fork函数的返回值 <2>创建子进程的目的 <3>代码共享 二、fork函数的相关问题 <1>为什么给父进程返回子进程的pid&#xff0c;给子进程…

数据生成 | Matlab实现基于DE差分进化算法的数据生成

数据生成 | Matlab实现基于DE差分进化算法的数据生成 目录 数据生成 | Matlab实现基于DE差分进化算法的数据生成生成效果基本描述模型描述程序设计参考资料 生成效果 基本描述 1.Matlab实现基于DE差分进化算法的数据生成&#xff0c;运行环境Matlab2021b及以上&#xff1b; 2.计…

代码随想录算法训练营Day46|LC139 单词拆分

一句话总结&#xff1a;完全背包&#xff01; 原题链接&#xff1a;139 单词拆分 动态规划之完全背包五部曲&#xff1a; 确定dp数组与下标含义&#xff1a;表示字符串长度为i时&#xff0c;dp[i] true 的话&#xff0c;可以拆分为一个或多个在字典中出现的单词。确定递归公…

C++相关概念和易错语法(4)(构造函数、析构函数)

一、构造函数 1.实现的功能&#xff1a;实例化对象的时候默认自动调用&#xff0c;相当于初始化。 条件&#xff1a;在书写时要满足构造函数的规范&#xff08;函数名 类名&#xff0c;不写返回值&#xff0c;也没有返回值&#xff09;&#xff0c;可以用inline来修饰。 2.自…

Microsoft Edge浏览器设置之后就很牛逼了

1.移除多余的广告 首先我们要先下载Microsoft Edge浏览器浏览器 然后在设置中先打开扩展,安装一个神奇的去广告插件 打开Edge 加载项 直接搜adguard 广告拦截器,直接获取就可以安装了,由于我已经安装过了,所以就是显示的删除。 2.解除网页复制限制 直接在扩展中安装sim…

Toyota Programming Contest 2024#4(AtCoder Beginner Contest 348)(A~D)

A - Penalty Kick i,1~N。如果 i 是 3 的倍数输出x&#xff0c;否则输出o #include <bits/stdc.h> //#define int long long #define per(i,j,k) for(int (i)(j);(i)<(k);(i)) #define rep(i,j,k) for(int (i)(j);(i)>(k);--(i)) #define debug(a) cout<<#…

HTTP详解及代码实现

HTTP详解及代码实现 HTTP超文本传输协议 URL简述状态码常见的状态码 请求方法请求报文响应报文HTTP常见的HeaderHTTP服务器代码 HTTP HTTP的也称为超文本传输协议。解释HTTP我们可以将其分为三个部分来解释&#xff1a;超文本&#xff0c;传输&#xff0c;协议。 超文本 加粗样…

开源 _ 新一代Android 性能监控框架Rabbit

最终扫描结果会展示如下: 点击右上角导出按钮可以把扫描结果以json的形式导出到SD卡中。 网络日志监控 rabbit可以记录网络请求日志并方便的查看返回的json数据: 卡顿日志监控 rabbit通过Choreographer来检测主线程的运行情况,并异步采集主线程堆栈来还原卡顿现场。 对于下…