【LeetCode 动态规划】买卖股票的最佳时机问题合集

文章目录

      • 1. 买卖股票的最佳时机含冷冻期
      • 2. 买卖股票的最佳时机Ⅳ ---- 只允许交易 k 次🖊

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

题目链接🔗
在这里插入图片描述


  • 🍎题目思路:
    在这里插入图片描述

在这里插入图片描述


  • 🍎题目代码:
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n + 1, vector(3, 0));dp[0][0] = 0, dp[0][1] = -prices[0], dp[0][2] = 0;for (int i = 1; i < n; i ++){// 第 i 天结束后处于冷冻期dp[i][0] = dp[i - 1][1] + prices[i];// 处于 买入dp[i][1] = max(dp[i - 1][2] - prices[i], dp[i - 1][1]);// 处于 可交易dp[i][2] = max(dp[i - 1][0], dp[i - 1][2]);}return max(dp[n - 1][0], dp[n - 1][2]);}
};



2. 买卖股票的最佳时机Ⅳ ---- 只允许交易 k 次🖊

题目链接🔗
在这里插入图片描述


  • 🍎题目思路:
    在这里插入图片描述

在这里插入图片描述


  • 🍎题目代码:
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n + 1, vector(k + 1, 0)); // 第 i 天结束后, 处于 买入状态vector<vector<int>> g(n + 1, vector(k + 1, 0)); // 第 i 天结束后, 处于 卖出状态// 初始化 f[][j]、g[][j]  第一天结束后, j 表示交易的次数, 第一天根本就不能完成一次交易// 为了避免对后续结果造成影响, 所以将其初始化为 -∞for (int j = 0; j <= k; j ++){f[0][j] = -0x3f3f3f3f;g[0][j] = -0x3f3f3f3f;}// 第 1 天结束后,处于买入状态f[0][0] = -prices[0];// 第 1 天结束后,处于卖出状态g[0][0] = 0;for (int i = 1; i < n; i ++){for (int j = 0; j <= k; j ++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);// 小优化:因为 j - 1 会越界// g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i])g[i][j] = g[i - 1][j];if (j - 1 >= 0)g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}int ans = g[n - 1][0];for (int i = 0; i <= k; i ++)ans = max(ans, g[n - 1][i]);return ans;}
};

在这里插入图片描述

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

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

相关文章

【面试八股总结】Redis数据结构及底层实现

一、五种基本数据结构 Redis 提供了丰富的数据类型&#xff0c;常见的有五种数据类型&#xff1a;String&#xff08;字符串&#xff09;&#xff0c;Hash&#xff08;哈希&#xff09;&#xff0c;List&#xff08;列表&#xff09;&#xff0c;Set&#xff08;集合&#xff0…

Studying-代码随想录训练营day14| 226.翻转二叉树、101.对称二叉树、104.二叉树的最大深度、111.二叉树的最小深度

第十四天&#xff0c;(ง •_•)ง&#x1f4aa;&#x1f4aa;&#xff0c;编程语言&#xff1a;C 目录 226.翻转二叉树 101.对称二叉树 100.相同的树 572.另一个树的子树 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 总结 226.翻转二叉树 文档讲…

建筑八大员证报名一寸彩色照片要求及手机自拍方法解读

在建筑行业&#xff0c;八大员证的持有者是广受尊重的专业人士。然而&#xff0c;要成为一名合格的八大员&#xff0c;首先必须通过资格审核和报名流程。其中重要的一步就是提交一寸彩色照片&#xff0c;以确保个人信息准确无误。那么&#xff0c;你是否清楚报名时照片的要求以…

milvus元数据解析工具milvusmetagui介绍使用

简介 milvusmetagui是一款用来对milvus的元数据进行解析的工具&#xff0c;milvus的元数据存储在etcd上&#xff0c;而且经过了序列化&#xff0c;通过etcd-manager这样的工具来查看是一堆二进制乱码&#xff0c;因此开发了这个工具对value进行反序列化解析。 在这里为了方便交…

深圳中小企业融资攻略,贷款方法大盘点!

中小企业融资这事&#xff0c;可不是一个简单的事情。资金对中小企业来说&#xff0c;就像血液对人体一样重要。企业发展离不开资金支持&#xff0c;特别是在今年这个环境下&#xff0c;政策对中小企业还挺友好的。今天讲解一下中小微企业常用的几种贷款方法。希望能让大家更明…

基于STM32和人工智能的自动驾驶小车系统

目录 引言环境准备自动驾驶小车系统基础代码实现&#xff1a;实现自动驾驶小车系统 4.1 数据采集模块4.2 数据处理与分析4.3 控制系统4.4 用户界面与数据可视化应用场景&#xff1a;自动驾驶应用与优化问题解决方案与优化收尾与总结 1. 引言 随着人工智能和嵌入式系统技术的…

pikachu靶场之XSS漏洞测试

一、环境配置 1.pikachu官网下载 下载地址&#xff1a;https://github.com/zhuifengshaonianhanlu/pikachu 2.百度网盘&#xff08;里面含有pikachu跟phpstudy&#xff09; 链接&#xff1a;pikachu下载 密码&#xff1a;abcd 配置&#xff1a;pikachu下载及安装-图文详解…

【尚庭公寓SpringBoot + Vue 项目实战】登录管理(十八)

【尚庭公寓SpringBoot Vue 项目实战】登录管理&#xff08;十八&#xff09; 文章目录 【尚庭公寓SpringBoot Vue 项目实战】登录管理&#xff08;十八&#xff09;1、登录业务介绍2、接口开发2.1、获取图形验证码2.2、登录接口2.3、获取登录用户个人信息 1、登录业务介绍 登…

keil5显示内存和存储占用百分比进度条工具

简介 [Keil5_disp_size_bar] 以进度条百分比来显示keil编译后生成的固件对芯片的内存ram和存储flash的占用情况, 并生成各个源码文件对ram和flash的占比整合排序后的map信息的表格和饼图。 原理是使用C语言遍历当前目录找到keil工程和编译后生成的map文件 然后读取工程文件和m…

shadertoy-安装和使用

一、安装vscode 安装vscode流程 二、安装插件 1.安装glsl编辑插件 2.安装shader toy插件 三、创建glsl文件 test.glsl文件 float Grid(float size, vec2 fragCoord) {vec2 r fragCoord / size;vec2 grid abs(fract(r - 0.5) - 0.5) / fwidth(r);float line min(grid…

Weevil-Optimizer象鼻虫优化算法的matlab仿真实现

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 Weevil-Optimizer象鼻虫优化算法的matlab仿真实现&#xff0c;仿真输出算法的优化收敛曲线&#xff0c;对比不同的适应度函数。 2.测试软件版本以及运行结果展示…

李宏毅2023机器学习作业HW06解析和代码分享

ML2023Spring - HW6 相关信息&#xff1a; 课程主页 课程视频 Sample code HW06 视频 HW06 PDF 个人完整代码分享: GitHub | Gitee | GitCode P.S. HW06 是在 Judgeboi 上提交的&#xff0c;出于学习目的这里会自定义两个度量的函数&#xff0c;不用深究&#xff0c;遵循 Sugge…

MySQL数据库的字段属性(navicat)

Unsigned&#xff1a;无符号 无符号的整数 声明了该列不能声明为负数 zerofill&#xff1a;填充零 不满足长度时&#xff0c;用0进行填充 如&#xff1a;int&#xff08;3&#xff09;&#xff0c;5 ——> 005 位置在无符号的下方 自增 通常理解为自增&…

《算法设计与分析》第五六章:回溯法与分支限界法

文章目录 回溯法分支限界法一、本章作业1.活动安排问题2.旅行商问题3.单源最短路径4.任务分配问题 二、算法积累1.回溯法求解01背包问题2.回溯法求解最大团问题3.回溯法求解n皇后问题4.回溯法求解地图着色5.回溯法求解哈密尔顿图6.回溯法求活动安排7.分支限界法求01背包问题8.分…

DIVE INTO DEEP LEARNING 36-49

文章目录 36. Data augmentation36.1 Training with enhanced data36.2 Enhancement measures36.3 Data augmentation summary 37. Fine tuning37.1 Fine tuning Introduce37.2 Fine tuning Step37.3 Fine tuning summary 38. Object detection38.1 Object detection38.2 Edge …

SpringBoot+Vue实现Excel文档导入和导出

1.准备工作 1.1.前端程序 在前端首先加上批量导出的按钮&#xff0c;如下 <el-button size"small" type"warning" plain click"exportData"> 批量导出 </el-button> 在添加了点击事件之后&#xff0c;在methods中要与之对应的添加上…

汽车IVI中控开发入门及进阶(二十七):车载摄像头vehicle camera

前言: 在车载IVI、智能座舱系统中,有一个重要的应用场景就是视频。视频应用又可分为三种,一种是直接解码U盘、SD卡里面的视频文件进行播放,一种是手机投屏,就是把手机投屏软件已视频方式投屏到显示屏上显示,另外一种就是对视频采集设备(主要就是摄像头Camera)的视频源…

3ds Max软件下载安装:3D建模软件 轻松开启你的建模之旅!

3ds Max&#xff0c;在建模过程中&#xff0c;网格建模和NURBS建模两大技术发挥着不可或缺的作用。网格建模允许用户通过顶点、边和面等元素的调整&#xff0c;精确地塑造出模型的形态&#xff1b;而NURBS建模则以其优秀的曲线和曲面处理能力&#xff0c;为设计师们提供了更为平…

二分+ST表+递推,Cf 1237D - Balanced Playlist

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1237D - Codeforces 二、解题报告 1、思路分析 case3提示我们一件事情&#xff1a;如果存在某个位置永远不停止&#xff0c;那么所有位置都满足永远不停止 很容易证明 随着下标右移&#xff0c…

【Ruby基础01】windows和termux中搭建Ruby开发环境

windows下环境搭建 railsinstaller官方git地址 按照文档安装git、nodejs、yarn&#xff0c;安装教程百度一下。railsinstall可以从release页面下载最新版本4.1.0。 安装完成如下 安装RubyMine 下载RubyMine RubyMine下载地址 安装激活 下载文件&#xff0c;按照里面的流程…