[Algorihm][简单多状态DP问题][买卖股票的最佳时机含冷冻期][买卖股票的最佳时机含手续费]详细讲解

目录

  • 1.买卖股票的最佳时机含冷冻期
    • 1.题目链接
    • 买卖股票的最佳时机含冷冻期
    • 2.算法原理详解
    • 3.代码实现
  • 2.买卖股票的最佳时机含手续费
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现


1.买卖股票的最佳时机含冷冻期

  • 1.题目链接

买卖股票的最佳时机含冷冻期

2.算法原理详解

  • 思路
    • 确定状态表示 -> dp[i][j]的含义:i -> 到了哪天,j -> 当天处于什么状态

      • dp[i][0]:第i天结束之后,处于"买入"状态,此时的最大利润
      • dp[i][1]:第i天结束之后,处于"可交易"状态,此时的最大利润
      • dp[i][2]:第i天结束之后,处于"冷冻期"状态,此时的最大利润
    • 推导状态转移方程:本题关系复杂,可以画图辅助

      • 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]
        请添加图片描述
    • 初始化:

      • dp[0][0] = -p[0], dp[0][1] = dp[0][2] = 0
    • 确定填表顺序:从左往右,一次填写三个表

    • 确定返回值:max(dp[n - 1][1], dp[n - 2][2])


3.代码实现

int maxProfit(vector<int>& prices) 
{int n = prices.size();vector<vector<int>> dp(n, vector<int>(3));dp[0][0] = -prices[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(dp[n - 1][1], dp[n - 1][2]);
}

2.买卖股票的最佳时机含手续费

1.题目链接

  • 买卖股票的最佳时机含手续费

2.算法原理详解

  • 思路
    • 确定状态表示 -> dp[i]的含义

      • i天结束之后,所能获得的最大利润
      • 本题,状态表示还可以继续细分:
        • f[i]:第i天结束之后,处于“买入”状态,此时的最大利润
        • g[i]:第i天结束之后,处于“卖出”状态,此时的最大利润
          请添加图片描述
    • 推导状态转移方程:本题关系复杂,可以画图辅助

      • f[i] = max(f[i - 1], g[i - 1] - p[i])
      • g[i] = max(g[i - 1], f[i - 1] + p[i] - fee)
        请添加图片描述
    • 初始化:

      • f[0] = -p[0], g[0] = 0
    • 确定填表顺序:从左往右,两个表一起填

    • 确定返回值:g[n - 1]


3.代码实现

int maxProfit(vector<int>& prices, int fee) 
{int n = prices.size();vector<int> f(n); // 买入vector<int> g(n); // 卖出f[0] = -prices[0];for(int i = 1; i < n; i++){f[i] = max(f[i - 1], g[i - 1] - prices[i]);g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);}return g[n - 1];
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2024年上半年软件设计师试题及答案(回忆版)

目录 基础知识选择题案例题1.缺陷识别的数据流图2.球队、球员、比赛记录的数据库题3.用户、老师、学生、课程用例图4.算法题5.程序设计题 基础知识选择题 树的节点&#xff0c;度为4的有4个&#xff0c;度为3的有8个&#xff0c;度为2个有6个&#xff0c;度为1的有10个&#x…

深入解析内置模块OS:让你的Python代码更懂操作系统

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、OS模块简介与基础应用 二、文件与目录操作详解 三、OS模块的高级应用&#xff1a;双色…

Kubectl 的使用——k8s陈述式资源管理

一、kebuctl简介: kubectl 是官方的CLI命令行工具&#xff0c;用于与 apiserver 进行通信&#xff0c;将用户在命令行输入的命令&#xff0c;组织并转化为 apiserver 能识别的信息&#xff0c;进而实现管理 k8s 各种资源的一种有效途径。 对资源的增、删、查操作比较方便&…

基础IO用户缓冲区 、inode、硬软链接【Linux】

文章目录 用户缓冲区磁盘磁盘分区EXT2文件系统的存储方案 inode软链接硬链接 用户缓冲区 代码一&#xff1a; 1 #include<stdio.h>2 #include<unistd.h>3 #include<string.h> 4 int main()5 {6 const char * fstr &…

孜然多程序授权系统V2.0开源

源码介绍 孜然一款多程序授权系统&#xff0c;支持自定义权限价格/新增程序配置等支持自动生成授权代码在线签到在线充值多支付接口IP/域名云黑文章系统&#xff08;富文本编辑器&#xff09;卡密功能一键云黑&#xff08;挂个大马/一键黑页/一键删库/一键删源码&#xff09; …

ROS2入门21讲__第07讲__节点:机器人的工作细胞

目录 前言 通信模型 案例一&#xff1a;Hello World节点&#xff08;面向过程&#xff09; 运行效果 代码解析 创建节点流程 案例二&#xff1a;Hello World节点&#xff08;面向对象&#xff09; 运行效果 代码解析 创建节点流程 案例三&#xff1a;物体识别节点 …

民国漫画杂志《时代漫画》第24期.PDF

时代漫画24.PDF: https://url03.ctfile.com/f/1779803-1248635000-177187?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!

GMSL2硬件设计V1.1

一、说明 GMSL(Gigabit Multimedia Serial Links),中文名称为千兆多媒体串行链路,是Maxim公司(现属于ADI)推出的一种高速串行接口,通过同轴电缆或屏蔽双绞线(STP)传输高速串行数据,用于汽车摄像头和显示器应用。GMSL2就是指ADI专有的第二代千兆多媒体串行链路技术,传输…

C++的哈希 哈希表 哈希桶

目录 Unordered系列关联式容器 什么是哈希 哈希表 闭散列 载荷因子α 扩容 查找 删除 字符串哈希算法 最终代码 开散列 插入 查找 删除 最终代码 完整代码 Unordered系列关联式容器 C98中&#xff0c;STL提供了底层为红黑树结构的一系列关联式容器&#xff0…

【数据结构】排序算法大全(快速、堆、归并、插入、折半、希尔、冒泡、计数、基数)各算法比较、解析+完整代码

文章目录 八、排序1.插入排序1.1 直接插入排序1.2 折半插入排序1.3 希尔排序 2.交换排序2.1 冒泡排序2.2 快速排序 3.选择排序3.1 简单选择排序3.2 堆3.2.1 堆排序3.2.2 堆插入删除*完善代码 堆 4.归并、基数、计数排序4.1 归并排序4.2 基数排序4.3 计数排序 5.内部排序算法的比…

基于遗传优化的Sugeno型模糊控制器设计matlab仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 5.完整工程文件 1.课题概述 基于遗传优化的Sugeno型模糊控制器设计matlab仿真,通过遗传优化算法优化模糊控制器的隶属函数参数&#xff0c;从而获得较优的控制效果。 2.系统仿真结果 3.核心程序与模型 …

如何将前端项目打包并部署到不同服务器环境

学习源码可以看我的个人前端学习笔记 (github.com):qdxzw/frontlearningNotes 觉得有帮助的同学&#xff0c;可以点心心支持一下哈&#xff08;笔记是根据b站尚硅谷的前端讲师【张天禹老师】整理的&#xff0c;用于自己复盘&#xff0c;有需要学习的可以去b站学习原版视频&…

新书推荐:7.3 for语句

本节必须掌握的知识点&#xff1a; 示例二十四 代码分析 汇编解析 7.3.1 示例二十四 ■for语句语法形式&#xff1a; for(表达式1;表达式2;表达式3) { 语句块; } ●语法解析&#xff1a; 第一步&#xff1a;执行表达式1&#xff0c;表达式1初始化循环变量&#xff1b; …

基于PHP的物业管理的设计与实现

第1章 绪论... 1 1.1 研究背景与意义... 1 1.2 国内外发展现状... 2 第2章 关键技术介绍... 3 2.1 PHP语言... 3 2.2 MySQL数据库... 3 2.3 Zend框架... 4 2.4 B/S架构... 4 第3章 系统需求分析... 5 3.1 可行性分析... 5 3.1.1 技术可行性分析... 5 3.1.2 经济可行…

IDEA 2024.1安装与破解

一、下载 官网地址&#xff1a;https://www.jetbrains.com/idea/download/other.html 二、安装 傻瓜式安装即可 三、破解 3.1 破解程序 网站&#xff1a;https://3.jetbra.in/ 3.2 获取激活码 点击*号部分即可复制成功

IOC控制反转

IOC IOC&#xff0c;全称为Inversion of Control(控制反转)&#xff0c;是一种设计原则&#xff0c;它反转了传统编程中的控制流程。在传统的编程模式中&#xff0c;组件之间的依赖关系是由组件自身在内部创建和维护的。而在控制反转模式中&#xff0c;这种依赖关系由外部容器(…

【Docker实战】进入四大数据库的命令行模式

上一篇我们讲了docker exec命令&#xff0c;这一次我们使用docker exec命令来进入四大数据库的命令行模式。 我们进行游戏开发或软件开发是离不开四大数据库的&#xff0c;这四大数据库分别是关系型数据库mysql、postgres&#xff0c;nosql数据库redis、mongodb。将它们容器化…

云上聚智——移动云云服务器进行后端的搭建及部署

什么是移动云 移动云是指将移动设备和云计算技术相结合&#xff0c;为移动应用提供强大的计算和存储能力的服务模式。传统的移动应用通常在本地设备上进行计算和存储&#xff0c;而移动云将这些任务转移到云端进行处理。通过移动云&#xff0c;移动设备可以利用云端的高性能计算…

【C++】——入门基础知识超详解

​​​​​​​ 目录 ​编辑 1.C关键字 2. 命名空间 2.1 命名空间定义 2.2 命名空间使用 命名空间的使用有三种方式&#xff1a; 注意事项 3. C输入&输出 示例 1&#xff1a;基本输入输出 示例 2&#xff1a;读取多个值 示例 3&#xff1a;处理字符串输入 示例…

神经网络不确定性综述(Part II)——Uncertainty estimation_Single deterministic methods

相关链接&#xff1a; 神经网络不确定性综述(Part I)——A survey of uncertainty in deep neural networks-CSDN博客 神经网络不确定性综述(Part II)——Uncertainty estimation_Single deterministic methods-CSDN博客 神经网络不确定性综述(Part III)——Uncertainty est…