代码随想录第四十九天|121. 买卖股票的最佳时机 、122.买卖股票的最佳时机II

news/2024/12/12 5:45:51/

121. 买卖股票的最佳时机

题目链接/文章讲解/视频讲解:https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html

1.代码展示

//121.股票的最佳买卖时机
int maxProfit(vector<int>& prices) {//step1.构建dp数组//dp[i][0]的含义是当前未持有股票时的余额//dp[i][1]的含义是当前持有股票的余额vector<vector<int>> dp(prices.size(), vector<int>(2, 0));if (prices.size() == 1) {return 0;}//step2 状态转移方程//未持有,可能是前一天的状态,也可能是今天卖掉的//dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])//持有,可能是前一天的状态,也可能是今天买的//dp[i][1] = max(dp[i - 1][1], -prices[i])//step3 初始化dp数组dp[0][0] = 0;dp[0][1] = -prices[0];//step4 开始遍历for (int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], -prices[i]);}return dp[prices.size() - 1][0];}

 2.本题小节

        思考:本题的需要明确的是状态转移方程的由来,每一天需要统计是否持有股票时的金额,因此每一天是有两个状态的,持有和不持有,dp[i][0]的含义是第i+1天没有持有股票时的金额,dp[i][1]的含义是第i+1天持有股票时的金额,通过分析可以知道,dp[i][0]由两种情况,一种是前一天就没有持有股票,另外一种情况是今天卖掉股票,因此对这两种情况取最大值,因此第i+1状态转移公式如代码中所示;同理,dp[i][1]也是两种情况,情况一是前一天就买了,情况二是当前天才买,注意当前天才买的话为-price[i],因为只能买卖一次,因此买的话就直接是-price[i]。最后返回未持股票的最后一位为答案。

        基本思路:补充一下,注意初始化。

122.买卖股票的最佳时机II 

 题目链接/文章讲解/视频讲解:代码随想录

1.代码展示

//122.股票的最佳买卖时机Ⅱ
int maxProfit(vector<int>& prices) {//step1.构建dp数组//dp[i][0]的含义是当前未持有股票时的余额//dp[i][1]的含义是当前持有股票的余额vector<vector<int>> dp(prices.size(), vector<int>(2, 0));if (prices.size() == 1) {return 0;}//step2 状态转移方程//未持有,可能是前一天的状态,也可能是今天卖掉的//dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])//持有,可能是前一天的状态,也可能是今天买的,今天买的那么昨天肯定未持有//dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])//step3 初始化dp数组dp[0][0] = 0;dp[0][1] = -prices[0];//step4 开始遍历for (int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[prices.size() - 1][0];}

2.本题小节

        思考:本题与上一题的区别是可以买卖多次,每次依然只能持有一张股票,因此也是只需要判断所持有或者不持有的状态,重点依然是状态转移方程,dp[i][0]与dp[i][1]的含义与上题是一样的,分析后发现,dp[i][0]与上一题一样,而dp[i][1]的第二种情况要使用上一天没买入来减,因为每次只能持有一张股票,因此上一天没买股票,当前天才能买股票,其他的都是一样的。 

 


http://www.ppmy.cn/news/1073805.html

相关文章

Node 使用 WebStorm 打开文件

Node 使用 WebStorm 打开文件 Node 脚本中, 打开文件. 如果有 WebStorm 就用 WebStorm 打开, 如果有 VSCode 就用 VSCode 打开, 否则 打开 目录 import { exec } from "child_process"; import fs from "fs-extra"; import open from "open";…

开源软件合集(Docker)

Docker安装 1.安装命令&#xff1a;curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun2.启动&#xff1a;systemctl start docker3.停止&#xff1a;systemctl stop docker4.重启&#xff1a;systemctl restart docker5.开机启动&#xff1a;systemctl enab…

【SpringBoot】最基础的项目架构(SpringBoot+Mybatis-plus+lombok+knife4j+hutool)

汝之观览&#xff0c;吾之幸也&#xff01; 从本文开始讲下项目中用到的一些框架和技术&#xff0c;最基本的框架使用的是SpringBoot(2.5.10)Mybatis-plus(3.5.3.2)lombok(1.18.28)knife4j(3.0.3)hutool(5.8.21),可以做到代码自动生成&#xff0c;满足最基本的增删查改。 一、新…

空时自适应处理用于机载雷达——额外的性能结果(Matla代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

js判断对象是否为空对象的方法总结

js判断对象是否为空对象的方法总结 方法1&#xff1a;JSON.stringify()方法方法2&#xff1a;for in方法方法3&#xff1a;Object.keys()方法方法4&#xff1a;Object.getOwnPropertyNames()方法方法5&#xff1a;jquery 的 isEmptyObject()方法 在面试或者开发过程中&#xff…

异或^实现数据加密

异或是一种二进制的位运算&#xff0c;符号以 XOR 或 ^ 表示。 1.1运算规则 相同为0&#xff0c;不同为1&#xff0c;即 1 ^ 1 0 0 ^ 0 0 1 ^ 0 1 由运算规则可知&#xff0c;任何二进制数与零异或&#xff0c;都会等于其本身&#xff0c;即 A ^ 0 A。 1.2 异或性质 …

linux使用不同的工具和命令来查看和放通允许访问的IP地址

在Linux系统中&#xff0c;您可以使用不同的工具和命令来查看和放通允许访问的IP地址。下面是一些常用的命令和方法&#xff1a; 查看当前开放的端口和规则&#xff1a; 使用 netstat 命令查看当前打开的端口和连接&#xff1a; Copy code netstat -tuln 使用 ss 命令也可以查…

SpringBoot初级开发--服务请求(GET/POST)所有参数的记录管理(8)

服务端在定位错误的时候&#xff0c;有时候要还原现场&#xff0c;这就要把当时的所有入参参数都能记录下来&#xff0c;GET还好说&#xff0c;基本NGINX都会记录。但是POST的请求参数基本不会被记录&#xff0c;这就需要我们通过一些小技巧来记录这些参数&#xff0c;放入日志…