当前位置: 首页 > 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()…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...