动态规划-状态机(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);}
}

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

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

相关文章

DevExpress WinForms图表组件 - 直观的数据信息呈现方式!(二)

在上文中&#xff08;点击这里回顾>>&#xff09;&#xff0c;我们为大家介绍了DevExpress WinForms图表控件的互动图表、图标设计器及可定制功能等&#xff0c;本文将继续介绍DevExpress WinForms图表控件的数据分析、大数据功能等&#xff0c;欢迎持续关注我们哦~ Dev…

力扣-350.两个数组的交集||

Idea 首先遍历第一个数组&#xff0c;用哈希表存储每个数字及其出现的次数。 然后遍历第二个数组&#xff0c;每出现重复的数字&#xff0c;并判断该数字在哈希表的次数是不是大于0&#xff0c;如果大于则存入答案数组&#xff0c;并将哈希表次数减1&#xff0c;直接遍历结束。…

pycharm中个人编程时常用到的快捷键

pycharm中个人编程时常用到的快捷键&#xff1a; 仅个人经验总结&#xff0c;不为其他&#xff01; 1.CTRLShiftAlt鼠标选择多个位置 可以同时在多个位置进行编辑同样的内容 2. Ctrel Alt L快速将代码格式标准化 3. Ctrl F 在当前py文件中查找 4. Ctrl R快速替换当前…

接口自动化中如何完成接口加密与解密?

加密是一种限制对网络上传输数据的访问权的技术。将密文还原为原始明文的过程称为解密&#xff0c;它是加密的反向处理。在接口开发中使用加密、解密技术&#xff0c;可以防止机密数据被泄露或篡改。在接口自动化测试过程中&#xff0c;如果要验证加密接口响应值正确性的话&…

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

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

C/C++字符函数和字符串函数详解————内存函数详解与模拟

个人主页&#xff1a;点我进入主页 专栏分类&#xff1a;C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 欢迎大家点赞&#xff0c;评论&#xff0c;收藏。 一起努力&#xff0c;一起奔赴大厂。 目录 1.前言 2 .memcpy函数 3.memmove函…

【Office】超简单,Excel快速完成不规则合并单元格排序

演示效果&#xff1a;将下图已经合并了的单元格按照单位名称排序并将同一个单位的数据合并在了一起。 Step 1&#xff1a;取消合并 选中所有的数据后&#xff0c;点击 “开始”-“合并单元格” &#xff0c;并且取消数据源的合并。 Step 2&#xff1a;填充数据 选中需要填…

【Go】go-es统计接口被刷数和ip访问来源

go-es模块统计日志中接口被刷数和ip访问来源 以下是使用go的web框架gin作为后端&#xff0c;展示的统计页面 背景 上面的数据来自elk日志统计。因为elk通过kibana进行展示&#xff0c;但是kibana有一定学习成本且不太能满足定制化的需求&#xff0c;所以考虑用编程的方式…

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…

国庆假期day5

作业&#xff1a;请写出七层模型及每一层的功能&#xff0c;请绘制三次握手四次挥手的流程图 1.OSI七层模型&#xff1a; 应用层--------提供函 表示层--------表密缩 会话层--------会话 传输层--------进程的接收和发送 网络层--------寻主机 数据链路层----相邻节点的可靠传…

【题解 动态规划】 Colored Rectangles

题目描述&#xff1a; 分析&#xff1a; 乍一看我还以为是贪心&#xff01; 猫 想想感觉没问题 但是局部最优并不能保证全局最优 比如这组数据 19 19 19 19 20 20 20 20如果按照贪心的做法&#xff0c;答案是20*20*2 但是其实答案是19*20*4 因此这道题用贪心是不对的 于是我…

Redis分页+多条件模糊查询组合实现思路

Redis是一个高效的内存数据库&#xff0c;它支持包括String、List、Set、SortedSet和Hash等数据类型的存储&#xff0c;在Redis中通常根据数据的key查询其value值&#xff0c;Redis没有模糊条件查询&#xff0c;在面对一些需要分页、排序以及条件查询的场景时(如评论&#xff0…

基于SSM的健身房管理系统

基于SSM的健身房管理系统的设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringSpringMVCMyBatis工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 【主要功能】 角色&#xff1a;管理员、用户 查看健身课程列表、新闻公告查看、推荐课程、购买…

《机器学习实战》学习记录-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…

【Leetcode】 131. 分割回文串

给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 1&#xff1a; 输入&#xff1a;s "aab" 输出&#xff1a;[["a","a"…

Spring Cloud Zuul 基本原理

Spring Cloud Zuul 底层是基于Servlet实现的&#xff0c;核心是通过一系列的ZuulFilter来完成请求的转发。 1、核心组件注册 1.1. EnableZuulProxy注解 启用Zuul作为微服务网关&#xff0c;需要在Application应用类加上EnableZuulProxy注解&#xff0c;而该注解核心是利用Im…

Web版Photoshop来了,用到了哪些前端技术?

经过 Adobe 工程师多年来的努力&#xff0c;并与 Chrome 等浏览器供应商密切合作&#xff0c;通过 WebAssembly Emscripten、Web Components Lit、Service Workers Workbox 和新的 Web API 的支持&#xff0c;终于在近期推出了 Web 版 Photoshop&#xff08;photoshop.adobe…

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

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

区块链3.0时代 基于GoMars构建的新概念TravelFi能否注入新力量?

区块链技术进入3.0时代 后疫情时代&#xff0c;全球数字化进程不断加快&#xff0c;世界范围内的移动通信、互联网技术及各类数字化应用的社会普及率也正在快速提升&#xff0c;疫情推动了互联网经济的增长&#xff0c;也让数字经济的价值开始显现。 数字经济一词的由来至今已经…

网络协议--概述

1.2 分层 网络协议通常分不同层次进行开发&#xff0c;每一层分别负责不同的通信功能。一个协议族&#xff0c;比如TCP/IP&#xff0c;是一组不同层次上的多个协议的组合。TCP/IP通常被认为是一个四层协议系统&#xff0c;如图1-1所示。 每一层负责不同的功能&#xff1a; 1.…