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

第九章 动态规划part12(代码随想录)

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

1. 确定dp数组(dp table)以及下标的含义

dp[i][j],第i天状态为j,所剩的最多现金为dp[i][j]。

2. 确定递推公式

拆分卖出股票状态是因为冷冻期前一天一定是具体卖出股票状态。

状态一 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], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);

不持有股票状态,这里就有两种卖出股票状态

状态二 dp[i][1]保持卖出股票的状态(两天前就卖出了股票,度过一天冷冻期。或者是前一天就是卖出股票状态,一直没操作

dp[i-1][1]

 

dp[i-1][3]

dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

状态三 dp[i][2]:今天具体卖出股票(前一天一定是持有股票状态才能卖)

dp[i-1][0] + prices[i]

dp[i][2] = dp[i - 1][0] + prices[i];

状态四 dp[i][3]:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!

dp[i-1][2] (前一天为具体卖出股票状态)

dp[i][3] = dp[i - 1][2];

3. dp数组如何初始化

如果是持有股票状态(状态一)那么:dp[0][0] = -prices[0],一定是当天买入股票。

dp[0][1] = ?

由于状态本身为非法状态。我们看递推公式中需要把它初始化成多少,就把它初始化成多少。

(1)用到了dp[0][1]:

 dp[i][0] = dp[i - 1][1] - prices[i];         (1)

Subsitutde i=1 into (1)

dp[1][0] = dp[0][1] - prices[1]; 第0天状态1初始化为0

dp[0][1] 初始化为0

让递推公式从第一天合理推导下去

同理:dp[0][2] = 0

dp[0][3] = 0 // 第0天就是冷冻期状态不合法

4. 确定遍历顺序

从前往后遍历

for (int i = 1; i < prices.size(); i++) {

持有股票的状态,此时手头现金一定不是最大的。最后一天的状态1、2、3都有可能是最大值。

最后结果:最后一天手头最大现金 max(dp[price.size()-1][1], dp[price.size()-1][2], dp[price.size()-1])[3])

5. 举例推导dp数组

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

 714.买卖股票的最佳时机含手续费 

相关文章:

第九章 动态规划part12(代码随想录)

309.最佳买卖股票时机含冷冻期 1. 确定dp数组&#xff08;dp table&#xff09;以及下标的含义 dp[i][j]&#xff0c;第i天状态为j&#xff0c;所剩的最多现金为dp[i][j]。 2. 确定递推公式 拆分卖出股票状态是因为冷冻期前一天一定是具体卖出股票状态。 状态一 dp[i][0]&…...

ssm珠宝首饰交易平台源码和论文

ssm珠宝首饰交易平台源码和论文101 开发工具&#xff1a;idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 技术&#xff1a;ssm 摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&a…...

交互设计都有哪些准则?

UI交互设计的本质不是完全基于用户的需求&#xff0c;而是交互设计师需要学习根据用户描述的产品形式来了解用户需要什么。 在交互设计过程中&#xff0c;遵循科学交互设计的本质是整个交互设计过程的重要组成部分&#xff0c;这与产品使用过程中给用户带来的体验密切相关。本…...

【MySQL】从哪几个角度分析数据库失败的原因?

总体评估MySQL服务器感谢 &#x1f496; 总体评估 当发现数据库出现问题时&#xff0c;我们首先应该从全局的角度考虑架构中的所有组件。包括&#xff1a; 服务器&#xff08;数据库和应用程序&#xff09; 存储&#xff1a;存储故障可能导致关键信息丢失网络接口&#xff1a…...

Spring Boot 的核心注解SpringBootApplication

SpringBootApplication 包括的注解 SpringBootConfiguration 组合了 Configuration 注解&#xff0c;实现配置文件的功能。 EnableAutoConfiguration 打开自动配置的功能&#xff0c;也可以关闭某个自动配置的选项&#xff0c; 例如&#xff1a;java 如关闭数据源自动配置功…...

自助式数据分析平台:JVS智能BI功能介绍(一)数据源

一、数据源配置 数据源概述 数据源是JVS-智能BI支持多种数据形态的基础&#xff0c;核心的目标是将不同的数据来源通过统一接入&#xff0c;实现将不同的数据实现统一的数据加工、数据应用。目前JVS-智能BI主要支持3种形态的数据&#xff1a;数据库、API、离线文件。 ​界面介…...

CSS魔术师Houdini,用浏览器引擎实现高级CSS效果

开门见山&#xff0c;直接上货 &#x1f50d; CSS Houdini是什么&#xff1f; “Houdini”一词引用自“Harry Houdini”&#xff0c;他是一位20世纪的著名魔术师&#xff0c;亦被称为史上最伟大的魔术师、逃脱术师及特级表演者。 我们都知道&#xff0c;浏览器在渲染网页显示样…...

DC/DC开关电源学习笔记(二)开关电源的分类

&#xff08;二&#xff09;开关电源的分类 1.DC/DC类开关电源2.AC/DC变换器3.电路结构分类4.功率开关管分类5.电路拓扑分类 根据变换方式&#xff0c;电源产品有下列四大类&#xff1b; &#xff08;1&#xff09;&#xff1a;第一大类&#xff1a;AC/DC开关电源&#xff1b; …...

conda创建python虚拟环境

1.查看当前存在那些虚拟环境 conda env list conda info -e 2.conda安装虚拟环境 conda create -n my_env_name python3.6 2.1在anaconda下改变python版本 当前3.7 安装3.7 conda create -n py37 python3.7 conda activate py37 conda create -n py37 python3.7conda a…...

Python 操作 MongoDB 数据库介绍

MongoDB 是一款面向文档型的 NoSQL 数据库&#xff0c;是一个基于分布式文件存储的开源的非关系型数据库系统&#xff0c;其内容是以 K/V 形式存储&#xff0c;结构不固定&#xff0c;它的字段值可以包含其他文档、数组和文档数组等。其采用的 BSON&#xff08;二进制 JSON &am…...

【ES6】Generator 函数

Generator 函数是 ES6 引入的一种新的函数类型&#xff0c;它既可以生成一个序列&#xff0c;又可以在某个条件下停止执行&#xff0c;并在需要时恢复执行。Generator 函数非常适合处理那些需要按需计算的场景&#xff0c;例如处理大数据、生成随机数等。 Generator 函数的基本…...

「操作系统」1. 基础

前言&#xff1a;操作系统基础八股文 文章目录 一 、操作系统基础1.1 什么是操作系统&#xff1f;1.2 什么是系统调用1.3 什么是中断 &#x1f680; 作者简介&#xff1a;作为某云服务提供商的后端开发人员&#xff0c;我将在这里与大家简要分享一些实用的开发小技巧。在我的职…...

Docker安装Oracl数据库!

安装Docker 查看是否安装docker: yum list installed | grep docker 安装docker: yum -y install docker 启动docker: systemctl start docker 查看docker启劝状态: systemctl status docker 查看docker版本: docker --version 设置docker开机自启动: systemctl en…...

QT子窗口为QWidget类型时,窗口背景不透明的实现方法

1...

leecode 数据库:1158. 市场分析 I

数据导入&#xff1a; SQL Schema&#xff1a; Create table If Not Exists Users (user_id int, join_date date, favorite_brand varchar(10)); Create table If Not Exists Orders (order_id int, order_date date, item_id int, buyer_id int, seller_id int); Create tab…...

简单shell脚本的编写

文章目录 简单使用shell脚本参数判断整数的比较运算符字符串的比较运算shell脚本流程控制shell脚本循环for循环批量添加用户批量ping IP地址检测同一局域网&#xff0c;多台主机存活情况检测同一局域网&#xff0c;多台主机存活情况多线程检测主机存活情况 while循环case选择语…...

汽车售后接待vr虚拟仿真实操演练作为岗位培训的重要工具和手段

汽车虚拟仿真教学软件是一种基于虚拟现实技术的教学辅助工具。它能够模拟真实的汽车环境和操作场景&#xff0c;让学生能够通过虚拟仿真来学习和实践汽车相关知识和技能。与传统的教学方式相比&#xff0c;汽车虚拟仿真教学软件具有更高的视觉沉浸感和互动性&#xff0c;能够更…...

登录校验-Filter-登录校验过滤器

目录 思路 登录校验Filter-流程 步骤 流程图 登录校验Filter-代码 过滤器类 工具类 测试登录 登录接口功能请求 其他接口功能请求 前后端联调 思路 前端访问登录接口&#xff0c;登陆成功后&#xff0c;服务端会生成一个JWT令牌&#xff0c;并返回给前端&#xff0…...

Vue3列表竖向滚动(包含使用swiper的翻页效果)

一、使用element-plus表格进行滚动&#xff1a; 可以满足的需求&#xff1a;表格一行一行竖向滚动&#xff0c;类似走马灯。 不能满足的需求&#xff1a;表格分页竖向滚动&#xff0c;有翻页的效果。 代码&#xff1a; <template><el-table:data"tableData"…...

OS 死锁处理

如果P先申请mutex 则mutex从1置零&#xff0c;假设申请到的empty 0则empty变成-1阻塞态 同理C中mutex从0变为-1&#xff0c;那么如果想离开阻塞态&#xff0c;那么就需要执行V&#xff08;empty&#xff09;但是如果执行V&#xff08;empty&#xff09;就需要P&#xff08;mu…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

是否存在路径(FIFOBB算法)

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

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...