《代码随想录》刷题打卡day36:动态规划-part09
【188. 买卖股票的最佳时机 IV】思路和上一题一样从2次交易变成了k次交易。注意dp[0] [j]当j为奇数的时候都初始化为 -prices[0]classSolution{public:intmaxProfit(intk,vectorintprices){intlenprices.size();vectorvectorintdp(len,vectorint(2*k1,0));/** dp[i][0]表示第i天没有操作所得最大金额 dp[i][1]表示第i天第一次持有股票所得最大金额 dp[i][2]表示第i天第一次不持有股票所得最大金额 dp[i][3]表示第i天第二次持有股票所得最大金额 dp[i][4]表示第i天第二次不持有股票所得最大金额 以此类推 **/for(inti1;i2*k;i2){dp[0][i]-prices[0];}for(inti1;ilen;i){// 2*i-1表示第i次持有股票的日子2*i表示第i次不持有股票的日子for(intj0;j2*k-1;j2){dp[i][j1]max(dp[i-1][j1],dp[i-1][j]-prices[i]);dp[i][j2]max(dp[i-1][j2],dp[i-1][j1]prices[i]);}}returndp[len-1][2*k];}};【309.买卖股票的最佳时机含冷冻期】动规五部曲分析如下确定dp数组以及下标的含义dp[i] [j]第i天状态为j所剩的最多现金为dp[i] [j]。本题搞得比较懵是因为出现冷冻期之后状态其实是比较复杂度例如今天买入股票、今天卖出股票、今天是冷冻期都是不能操作股票的。具体可以区分出如下四个状态状态一持有股票状态今天买入股票或者是之前就买入了股票然后没有操作一直持有不持有股票状态这里就有两种卖出股票状态状态二保持卖出股票的状态两天前就卖出了股票度过一天冷冻期。或者是前一天就是卖出股票状态一直没操作状态三今天卖出股票状态四今天为冷冻期状态但冷冻期状态不可持续只有一天「今天卖出股票」我是没有单独列出一个状态的归类为「不持有股票的状态」而本题为什么要单独列出「今天卖出股票」 一个状态呢因为本题我们有冷冻期而冷冻期的前一天只能是 「今天卖出股票」状态如果是 「不持有股票状态」那么就很模糊因为不一定是 卖出股票的操作。注意这里的每一个状态例如状态一是持有股票股票状态并不是说今天一定就买入股票而是说保持买入股票的状态即可能是前几天买入的之后一直没操作所以保持买入股票的状态。确定递推公式达到买入股票状态状态一即dp[i] [0]有两个具体操作操作一前一天就是持有股票状态状态一dp[i] [0] dp[i - 1] [0]操作二今天买入了有两种情况前一天是冷冻期状态四dp[i - 1] [3] - prices[i]前一天是保持卖出股票的状态状态二dp[i - 1] [1] - prices[i]那么dp[i] [0] max(dp[i - 1] [0], dp[i - 1] [3] - prices[i], dp[i - 1] [1] - prices[i]);达到保持卖出股票状态状态二即dp[i] [1]有两个具体操作操作一前一天就是状态二操作二前一天是冷冻期状态四dp[i] [1] max(dp[i - 1] [1], dp[i - 1] [3]);达到今天就卖出股票状态状态三即dp[i] [2] 只有一个操作昨天一定是持有股票状态状态一今天卖出即dp[i] [2] dp[i - 1] [0] prices[i];达到冷冻期状态状态四即dp[i] [3]只有一个操作昨天卖出了股票状态三dp[i] [3] dp[i - 1] [2];dp数组如何初始化这里主要讨论一下第0天如何初始化。如果是持有股票状态状态一那么dp[0] [0] -prices[0]一定是当天买入股票。保持卖出股票状态状态二这里其实从 「状态二」的定义来说 很难明确应该初始多少这种情况我们就看递推公式需要我们给他初始成什么数值。如果i为1第1天买入股票那么递归公式中需要计算 dp[i - 1] [1] - prices[i] 即 dp[0] [1] - prices[1]那么大家感受一下 dp[0] [1] 即第0天的状态二应该初始成多少只能初始为0。想一想如果初始为其他数值是我们第1天买入股票后 手里还剩的现金数量是不是就不对了。今天卖出了股票状态三同上分析dp[0] [2]初始化为0dp[0] [3]也初始为0。确定遍历顺序从递归公式上可以看出dp[i] 依赖于 dp[i-1]所以是从前向后遍历。举例推导dp数组classSolution{public:intmaxProfit(vectorintprices){intlenprices.size();vectorvectorintdp(len,vectorint(4,0));// dp[i][0]表示第i天持有股票的最大现金// dp[i][1]表示第i天不持有股票的最大现金保持卖出股票状态// dp[i][2]表示第i天不持有股票的最大现金当天卖出股票// dp[i][3]表示第i天为冷冻期的最大现金前一天刚卖出股票只有一天不可持续dp[0][0]-prices[0];for(inti1;ilen;i){dp[i][0]max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));dp[i][1]max(dp[i-1][1],dp[i-1][3]);dp[i][2]dp[i-1][0]prices[i];dp[i][3]dp[i-1][2];}returnmax(dp[len-1][1],max(dp[len-1][2],dp[len-1][3]));}};【714.买卖股票的最佳时机含手续费】思路比较清晰减掉手续费即可。classSolution{public:intmaxProfit(vectorintprices,intfee){intlenprices.size();vectorvectorintdp(len,vectorint(2,0));// dp[i][0]表示第i天持有股票的最大现金// dp[i][1]表示第i天不持有股票的最大现金dp[0][0]-prices[0];for(inti1;ilen;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][0]prices[i]-fee);}returndp[len-1][1];}};

相关新闻

智能燃气灶深度拆解:从语音控制到防干烧的安全技术指南

智能燃气灶深度拆解:从语音控制到防干烧的安全技术指南

厨电智能化已经不算新鲜事了,但真正把“智能”做到实用的产品并不多。最近在帮朋友挑选燃气灶时,仔细研究了一下火王智能灶这款产品,发现它把语音控制、智能关火、防干烧、定时、大火力这些功能整合到了一起,和传统燃气灶相比&…

2026/11/21 21:42:46 阅读更多 →
基于STM32的全自动节水灌溉系统:从传感器选型到状态机实现

基于STM32的全自动节水灌溉系统:从传感器选型到状态机实现

简介:本资源是一套完整的基于STM32的全自动节水灌溉系统毕业设计实现方案,面向计算机、自动化、通信及人工智能等相关专业学生与教师,解决农业物联网场景下土壤湿度感知、智能启停灌溉、远程数据上报等核心问题,适用于课程设计、大…

2026/11/21 21:42:46 阅读更多 →
ROS2机器人开发实战:从通信契约到真机部署的系统工程指南

ROS2机器人开发实战:从通信契约到真机部署的系统工程指南

最近在整理一个机器人项目时,我翻出了几年前用ROS1写的代码。看着那些复杂的launch文件和需要手动编译的包,一个念头冒了出来:如果现在从头开始,我还会选择同样的路径吗?答案大概率是否定的。不是因为ROS1不好&#xf…

2026/11/21 12:01:06 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻