当前位置: 首页 > news >正文

动态规划-状态机(188. 买卖股票的最佳时机 IV)

状态分类:

f[i,j,0]考虑前i只股票,进行了j笔交易,目前未持有股票 所能获得最大利润

f[i,j,1]考虑前i只股票,进行了j笔交易,目前持有股票 所能获得最大利润

状态转移:

f[i][j][0] = Math.max(f[i-1][j][0],f[i-1][j][1]+prices[i]);

f[i][j][1] = Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i]);

 

class Solution {static int INF = 0x3f3f3f3f;public int maxProfit(int k, int[] prices) {int n = prices.length;int f[][][] = new int[n+1][k+1][2];for(int i = 0;i <= n;i++){for(int j = 0;j <= k;j++){Arrays.fill(f[i][j],-INF);}}for(int i = 0;i <= n;i++)f[i][0][0] = 0;for(int i = 1;i <= n;i++){for(int j = 1;j <= k;j++){f[i][j][0] = Math.max(f[i-1][j][0],f[i-1][j][1]+prices[i-1]);f[i][j][1] = Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]);}}int ans = 0;for(int i = 0;i <= k;i++){ans = Math.max(ans,f[n][i][0]);}return ans;}
}

还有一位大佬的看不懂的极妙解法--滚动的dp?

// java
class Solution {public int maxProfit(int k, int[] prices) {int[] buy = new int[k], sell = new int[k];Arrays.fill(buy, -prices[0]);for (int i = 1; i < prices.length; i++) {for (int j = 0, pre = 0; j < k; j++) {buy[j] = (pre = Math.max(buy[j], pre - prices[i]));sell[j] = (pre = Math.max(sell[j], pre + prices[i]));}}return Math.max(sell[k - 1], 0);}
}

相关文章:

动态规划-状态机(188. 买卖股票的最佳时机 IV)

状态分类&#xff1a; f[i,j,0]考虑前i只股票&#xff0c;进行了j笔交易&#xff0c;目前未持有股票 所能获得最大利润 f[i,j,1]考虑前i只股票&#xff0c;进行了j笔交易&#xff0c;目前持有股票 所能获得最大利润 状态转移&#xff1a; f[i][j][0] Math.max(f[i-1][j][0],f[…...

银行业务队列简单模拟(队列应用)

设某银行有A、B两个业务窗口&#xff0c;且处理业务的速度不一样&#xff0c;其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时&#xff0c;B窗口处理完1个顾客。给定到达银行的顾客序列&#xff0c;请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时…...

2023/8/8 下午10:42:04 objectarx

2023/8/8 下午10:42:04 objectarx 2023/8/8 下午10:42:16 ObjectARX(AutoCAD Runtime Extension)是用于开发和自定义AutoCAD软件的编程接口。ObjectARX允许开发者使用C++、.NET等编程语言来创建插件、扩展功能和定制化AutoCAD的行为。 通过ObjectARX,开发者可以访问Auto…...

Day-06 基于 Docker安装 Nginx 镜像

1.去官方公有仓库查询nginx镜像 docker search nginx 2.拉取该镜像 docker pull nginx 3. 启动镜像&#xff0c;使用nginx服务&#xff0c;代理本机8080端口(测试是不是好使) docker run -d -p 8080:80 --name nginx-8080 nginx docker ps curl 127.0.0.1:8080...

linux入门---信号的保存和捕捉

目录标题 信号的一些概念信号的保存pending表block表handler表 信号的捕捉内核态和用户态信号的捕捉 信号的一些概念 1.进程会收到各种各样的信号&#xff0c;那么程序对该信号进行实际处理的动作叫做信号的递达。 2.我们之前说过当进程收到信号的时候可能并不会立即处理这个信…...

5.外部中断

中断初始化配置步骤&#xff1a; IO口初始化配置 开启中断总允许EA 打开某个IO口的中断允许 打开IO口的某一位的中断允许 配置该位的中断触发方式 中断函数&#xff1a; #pragma vector PxINT_VECTOR __interrupt void 函数名(void){}#pragma vector PxINT_VECTOR __int…...

Mydb数据库问题

1、请简要介绍一下这个基于 Java 的简易数据库管理系统。它的主要功能是什么&#xff1f; TM&#xff08;Transaction Manager&#xff09;&#xff1a;事务管理器&#xff0c;用于维护事务的状态&#xff0c;并提供接口供其他模块查询某个事务的状态。DM&#xff08;Data Man…...

部署并应用ByteTrack实现目标跟踪

尽管YOLOv8已经集成了ByteTrack算法&#xff0c;但在这里我还是想利用ByteTrack官网的代码&#xff0c;自己实现目标跟踪。 要想应用ByteTrack算法&#xff0c;首先就要从ByteTrack官网上下载并安装。虽然官网上介绍得很简单&#xff0c;只需要区区6行代码&#xff0c;但对于国…...

MacOS怎么配置JDK环境变量

1 输入命令看是否配置了JDk 的环境变量&#xff1a;echo $JAVA_HOME 要是什么也没输出 证明是没配置 2 输入命令编辑 sudo vim ~/.bash_profile 然后按 i &#xff0c;进入编辑模式&#xff0c;粘贴下面的代码&#xff0c;注意&#xff1a;JAVA_HOME后面路径需要改成自己的版…...

Spring Boot 开发16个实用的技巧

当涉及到使用Spring Boot开发应用程序时&#xff0c;以下是16个实用的技巧&#xff1a; 1. **使用Spring Initializr**&#xff1a;Spring Initializr是一个快速创建Spring Boot项目的工具&#xff0c;可以帮助您选择项目依赖和生成项目骨架。 2. **自动配置**&#xff1a;Sp…...

《机器学习实战》学习记录-ch2

PS: 个人笔记&#xff0c;建议不看 原书资料&#xff1a;https://github.com/ageron/handson-ml2 2.1数据获取 import pandas as pd data pd.read_csv(r"C:\Users\cyan\Desktop\AI\ML\handson-ml2\datasets\housing\housing.csv")data.head() data.info()<clas…...

lv7 嵌入式开发-网络编程开发 07 TCP服务器实现

目录 1 函数介绍 1.1 socket函数 与 通信域 1.2 bind函数 与 通信结构体 1.3 listen函数 与 accept函数 2 TCP服务端代码实现 3 TCP客户端代码实现 4 代码优化 5 练习 1 函数介绍 其中read、write、close在IO中已经介绍过&#xff0c;只需了解socket、bind、listen、acc…...

mysql技术文档--阿里巴巴java准则《Mysql数据库建表规约》--结合阿丹理解尝试解读--国庆开卷

阿丹&#xff1a; 国庆快乐呀大家&#xff01; 在项目开始前一个好的设计、一个健康的表关系&#xff0c;不仅会让开发变的有趣舒服&#xff0c;也会在后期的维护和升级迭代中让系统不断的成长。那么今天就认识和解读一下阿里的准则&#xff01;&#xff01; 建表规约 表达是…...

Qt+openCV学习笔记(十六)Qt6.6.0rc+openCV4.8.1+emsdk3.1.37编译静态库

前言&#xff1a; 有段时间没来写文章了&#xff0c;趁编译库的空闲&#xff0c;再写一篇记录文档 WebAssembly的发展逐渐成熟&#xff0c;即便不了解相关技术&#xff0c;web前端也在不经意中使用了相关技术的库&#xff0c;本篇文档记录下如何编译WebAssembly版本的openCV&…...

JUC第十四讲:JUC锁: ReentrantReadWriteLock详解

JUC第十四讲&#xff1a;JUC锁: ReentrantReadWriteLock详解 本文是JUC第十四讲&#xff1a;JUC锁 - ReentrantReadWriteLock详解。ReentrantReadWriteLock表示可重入读写锁&#xff0c;ReentrantReadWriteLock中包含了两种锁&#xff0c;读锁ReadLock和写锁WriteLock&#xff…...

在vue3中使用vite-svg-loader插件

vite-svg-loader插件可以让我们像使用vue组件那样使用svg图&#xff0c;使用起来超级方便。 安装 npm install vite-svg-loader --save-dev使用 import svgLoader from vite-svg-loaderexport default defineConfig({plugins: [vue(), svgLoader()] })组件里使用 在路径后加…...

国庆10.4

QT实现TCP服务器客户端 服务器 头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTcpServer> //服务器头文件 #include <QTcpSocket> //客户端头文件 #include <QList> //链表容器 #include <QMe…...

2023/8/12 下午8:41:46 树状控件guilite

2023/8/12 下午8:41:46 树状控件guilite 2023/8/12 下午8:42:08 树状控件(Tree View)是一种常见的图形用户界面(GUI)元素,它通常用于显示层次结构数据或文件系统的目录结构。Guilite 是一个轻量级的跨平台 GUI 库,支持多种控件,包括树状控件。 在 Guilite 中使用树状…...

BL808学习日志-2-LVGL for M0 and D0

一、lvgl测试环境 对拿到的M1S_DOCK开发板进行开发板测试&#xff0c;博流的官方SDK是支持M0和D0两个内核都进行测试的&#xff1b;但是目前只实现了M0的LVGLBenchmark&#xff0c;测试D0内核中发现很多莫名其妙的问题。一会详细记录。 使用的是开发板自带的SPI显示屏&#xff…...

treectrl类封装 2023/8/13 下午4:07:35

2023/8/13 下午4:07:35 treectrl类封装 2023/8/13 下午4:07:53 TreeCtrl 类是一个常用的图形用户界面控件,用于实现树形结构的展示和交互。以下是一个简单的 TreeCtrl 类的封装示例: python import wxclass MyTreeCtrl(wx.TreeCtrl):def __init__(self, parent):super()…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...