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

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...