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

DAY53:动态规划(买股票的最佳时机)

 Leetcode: 121 买卖股票的最佳时机

代码随想录

1、确定下标和含义

dp[i][0]表示当天持有股票所得的最多现金

do[i][1]表示当天不持有股票的最多现金

2、递推公式

(1)如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • 第i天买入股票,所得现金就是买入今天的股票后所得现金即:-prices[i]

那么dp[i][0]应该选所得现金最大的,所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

(2)如果第i天不持有股票即dp[i][1], 也可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]

第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金即:prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的,dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

3、初始化

dp[0][0]表示第0天持有股票,此时的持有股票就一定是买入股票了,所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票,不持有股票那么现金就是0,所以dp[0][1] = 0;

时间复杂度:O(n)

空间复杂度:O(n)

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if(len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for(int i = 1; i < len; i++){dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];//最后肯定卖出}
};

Leetcode: 122 买卖股票的最佳时机II

与上题不同的是,这道题可以反复卖出股票。

所以就体现在状态公式上

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去今天的股票价格 即:dp[i - 1][1] - prices[i]

(2)如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来

  • 第i-1天就不持有股票,那么所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
  • 第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金即:prices[i] + dp[i - 1][0]

时间复杂度:O(n)

空间复杂度:O(n)

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[len - 1][1];}
};

之前我们用贪心的方法做过这道题,所以可以回顾一下。

相关文章:

DAY53:动态规划(买股票的最佳时机)

Leetcode: 121 买卖股票的最佳时机 代码随想录 1、确定下标和含义 dp[i][0]表示当天持有股票所得的最多现金 do[i][1]表示当天不持有股票的最多现金 2、递推公式 &#xff08;1&#xff09;如果第i天持有股票即dp[i][0]&#xff0c; 那么可以由两个状态推出来 第i-1天就…...

快速实现用户认证:使用Python和Flask配合PyJWT生成与解密Token的教程及示例代码

生成token 与解密 token 和 拦截器 #学习交流 访问 # https://v.iiar.cnimport jwt import datetime from models import XUser from flask import request, jsonify from functools import wrapsSECRET_KEY XPay# 创建token def generate_token(user_id):try:payload {exp:…...

外汇110:外汇做空是什么意思?如何运作?一文读懂

外汇市场允许卖空&#xff0c;就像众多金融市场一样。但什么是卖空呢&#xff1f;如何外汇做空&#xff1f;在本文中&#xff0c;我们将讨论如何做空货币。什么是外汇做空&#xff1f; 外汇做空&#xff08;Short Selling&#xff09;是外汇市场上的一种投资方式。它指的是投资…...

【记录】个人博客或笔记中的数学符号设定

note 这里记录个人博客中常用的数学符号数学格式和对应含义 文章目录 note数与数组索引集合线性代数微积分概率和信息论数据与概率分布函数深度学习中的常用数学表达方式 数与数组 α 标量 α 向量 A 矩阵 A 张量 I n n 行 n 列单位矩阵 v w 单词 w 的分布式向量表示 …...

Redis Sentinel工作原理

Redis Sentinel是Redis的高可用性解决方案。它主要用来监控Redis master和slave服务器的运行状态&#xff0c;并在master宕机时自动进行故障转移&#xff0c;即从slave节点中选举出新的master节点&#xff0c;并让其余的slave节点指向新的master节点。 Redis Sentinel工作原理…...

GEE入门篇|遥感专业术语:理论介绍

本章的目的是介绍遥感图像的一些主要特征&#xff0c;以及如何在Earth Engine中检查它们。我们将讨论空间分辨率、时间分辨率和光谱分辨率&#xff0c;以及如何访问重要的图像元数据。将了解到来自不同卫星平台上的几个传感器的图像数据。在本章的学习完成后&#xff0c;您将能…...

react中如何做到中断diff过程和恢复

workLoop是 实现时间切片 和 可中断渲染的核心&#xff0c;简要说明如下&#xff1a; // 并发任务的入口function workLoopConcurrent() {// Perform work until Scheduler asks us to yield// 有任务 & 是否需要中断while (workInProgress ! null && !shouldYiel…...

python:PyPDF2 从PDF文件中提取目录

我发现 pypdf 和 pypdf2 的作者是同一人&#xff1a;Mathieu Fenniak pip install pypdf2 ; pypdf2-3.0.1-py3-none-any.whl (232 kB) 编写 pdf_read_dir.py 如下 # -*- coding: utf-8 -*- """ pypdf23.0.1 从PDF中提取目录 """ import os…...

Java 2:运算符、表达式和语句

2.1 运算符与表达式 Java提供了丰富的运算符&#xff0c;如算术运算符、关系运算符、逻辑运算符、位运算符等。Java语言中的绝大多数运算符和C语言相同&#xff0c;基本语句如条件分支语句&#xff0c;循环语句等&#xff0c;也和C语言类似。 2.1.1算术运算符与算术表达式 1…...

批量提取word文件中文本框内容的三种方法

一、问题的提出 在日常的办公中&#xff0c;有时需要提取多个word文件中的文字框的内容。有时&#xff0c;文字框的数量比较多&#xff0c;而且处于文档的不同位置&#xff0c;手工提取比较耗时耗力&#xff0c;同时也可能会产生遗漏。 我们也可以通过VBA和Python来解决这个问…...

Leecode之合并两个有序链表

一.题目及剖析 https://leetcode.cn/problems/merge-two-sorted-lists/description/ 二.思路引入 用指针遍历两个链表并实时比较,较小的元素进行尾插,然后较小元素的指针接着向后遍历 三.代码引入 /*** Definition for singly-linked list.* struct ListNode {* int va…...

陶建国教授谈中西方文化的差异与交融

龙年到来&#xff0c;这个春节里&#xff0c;“龙”字的英文翻译引发关注&#xff0c;冲上了热搜&#xff0c;网友发现&#xff0c;“龙”不再翻译为“dragon”&#xff0c;而是龙字的谐音“loong”。原来&#xff0c;在西方人的眼里&#xff0c;龙是凶猛的怪兽&#xff0c;具有…...

Ps:画笔选项

画笔选项 Brush Options提供了对画笔&#xff08;圆形笔刷&#xff09;基本属性的控制&#xff0c;比如大小、硬度、间距、角度和圆度等。 Photoshop 中的快速选择工具、污点修复画笔工具、修复画笔工具、颜色替换工具、背景橡皮擦工具等的工具选项栏上提供了这种圆形笔刷选项。…...

嵌入式——Flash(W25Q64)

目录 一、初识W25Q64 1. 基本认识 2. 引脚介绍 ​编辑 二、W25Q64特性 1. SPI模式 2. 双输出SPI方式 三、状态寄存器 1. BUSY位 2. WEL位 3. BP2、BP1、 BP0位 4. TB位 5. 保留位 6. SRP位 四、常用操作指令 1. 写使能指令&#xff08;06h&#xff09; 2. 写禁…...

stm32:pwm output模块,记录一下我是用smt32,输出pwm波的记录--(实现--重要)

我是实现了输出pwm波,频率固定,占空比可以不断调整的方法,将PA0接到示波器上,可以看到是一个标准的PWM波,如图下面示波器图。 1,首先是ioc的配置 我刚开始设置的分频的倍数是7199,使得分频的太大了,示波器显示不了,最后修改为71就可以,我之前设置读取pwm也是一样的…...

phpstrom创建thinkphp项目

安装php和composer 参考 安装phpstrom 创建项目 查看thinkphp版本 https://packagist.org/packages/topthink/think 打开所在项目编辑配置 即可调试运行...

【Linux】线程同步

线程同步 一、条件变量1. 同步概念2. 条件变量概念3. 条件变量接口&#xff08;1&#xff09;pthread_cond_init()&#xff08;2&#xff09;pthread_cond_destroy()&#xff08;3&#xff09;pthread_cond_wait()&#xff08;4&#xff09;pthread_cond_signal()&#xff08;5…...

如何在多头自注意力机制的交叉学习中引入对于物理、生理、心理世界客观规律的对照验证...

要在多头自注意力机制的交叉学习中引入对于物理世界客观规律的对照验证&#xff0c;可以考虑以下方法&#xff1a; 1、引入物理模型 首先&#xff0c;建立一个物理模型&#xff0c;该模型能够描述物理世界中的客观规律。这个模型可以是已知的科学理论&#xff0c;也可以是通过实…...

智慧公厕:让智慧城市的公共厕所焕发“智慧活力”

智慧城市的建设已经进入了一个新的阶段&#xff0c;不仅仅是智慧交通、智慧环保&#xff0c;如今甚至连公厕都开始迎来智慧化时代。智慧公厕作为智慧城市的神经末梢&#xff0c;正在通过信息化、数字化和智慧化的方式&#xff0c;实现全方位的精细化管理。本文以智慧公厕源头专…...

vue导出word文档(图文示例)

第076个 查看专栏目录: VUE 本文章目录 示例说明示例效果图导出的文件效果截图示例源代码参数说明&#xff1a;重要提示&#xff1a;API 参考网址 示例说明 在Vue中导出Word文档&#xff0c;可以使用第三方库file-saver和html-docx-js。首先需要安装这两个库&#xff1a; npm …...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...