代码随想录算法训练营第四十八天 | LeetCode 121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 II

简介: 代码随想录算法训练营第四十八天 | LeetCode 121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 II

代码随想录算法训练营第四十八天 | LeetCode 121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 II

文章链接:买卖股票的最佳时机买卖股票的最佳时机 II

视频链接:买卖股票的最佳时机买卖股票的最佳时机 II

1. LeetCode 121. 买卖股票的最佳时机

1.1 思路

  1. 在本题中我们要通过买卖一次股票而赚的最多。股票买卖问题是动态规划解决的比较经典的一系列,可能这题也能用贪心或者别的思路解决,但这些只能解决具体场景的题目,动态规划是解决一系列的题目。
  2. dp 数组及其下标的含义:第 i 天有两个状态买与不买这只股票,因此需要定义二维数组 dp[i][0]:表示持有这只股票,所得的最大现金;dp[i][1]:表示不持有这只股票,所得的最大现金。最终求的结果就是 dp[length-1][0] 和 dp[length-1][1] 两个状态中取最大值。注意:我们是第 i 天持有股票,很可能第 i 天之前就买了,第 i 天不持有也不代表第 i 天卖出,很可能第 i 天之前就卖出了。
  3. 递推公式:dp[i][0] 中:我们中 dp[i-1][0] 时是不是就可以已经持有这只股票的最大现金,也就是一直延续着这种状态,现金就没有改变了,此时 dp[i][0]=dp[i-1][0];还有一种情况就是第 i 天买入这只股票了,此时就变成了持有这只股票的状态了,就需要把这个对应的钱花出去,因此现金要减去 price[i],而本题股票只买入一次,因此直接就是 dp[i][0]=0-prices[i],因此 dp[i][0]=两者最大值,因为我们要求最大现金。
  4. dp[i][1] 中:同理也可以保持前一天的状态,即第 i-1 天也不持有这只股票,dp[i][1]=dp[i-1][1];还有一种情况就是在第 i 天卖出这只股票了,此时就变成了不持有这只股票的状态了,那第 i-1 天就一定是持有这只股票的状态了即 dp[i-1][0],再加上第 i 天卖出股票的价格 prices[i],因此 dp[i][1]=两者最大值
  5. dp 数组的初始化:从递推公式可以看出,dp[i] 都是由 dp[i-1] 推出的,都是依靠前一个状态的,因此,dp[0][0] 和 dp[0][1] 这两个状态是最基础的状态,第一个是第 0 天持有这只股票的最大现金,那就是负的了,即-prices[0],第二个是第 0 天不持有这只股票的最大现金,那也还是 0
  6. 遍历顺序:根据滴推公式则是从前往后遍历 for(int i=1;i<length;i++)为什么从 1 开始,因为 0 已经初始化了
  7. 打印 dp 数组:用于 debug

1.2 代码

// 解法1
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int length = prices.length;
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[length][2];
        int result = 0;
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[length - 1][1];
    }
}

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

2.1 思路

  1. 121. 买卖股票的最佳时机区别在于股票可以买卖多次了,问最大利润是多少。可以使用贪心思路,甚至更简单了,但用动态规划更加有继承性。
  2. 递推公式:先看不持有这只股票的状态 dp[i][1]:可以由 dp[i-1][1] 或者 dp[i-1][0]+prices[i] 推导而来,这个和121. 买卖股票的最佳时机是一样的。再看持有这只股票的状态 dp[i][0]:可以由第 i-1 天持有股票的状态延续下来即 dp[i-1][0],也可以第 i 天买入股票,而买入股票这种状态中121. 买卖股票的最佳时机中是全程只能买卖一次股票,因此是 0-prices[i],而本题是可以多次买卖的,手头上的现金就不是 0 了,就应该是第 i-1 天不持有股票的最大现金了即 dp[i-1][1],再减去 prices[i],即 dp[i][0]=两者最大值,这就是本题和121. 买卖股票的最佳时机的唯一区别,其他的同上一题

2.2 代码

// 动态规划
class Solution 
    // 实现1:二维数组存储
    // 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储
    // 时间复杂度:O(n),空间复杂度:O(n)
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];     // 创建二维数组存储状态
        dp[0][0] = 0;                   // 初始状态
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);    // 第 i 天,没有股票
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 第 i 天,持有股票
        }
        return dp[n - 1][0];    // 卖出股票收益高于持有股票收益,因此取[0]
    }
}
目录
打赏
0
0
1
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
102 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
6月前
|
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
94 7

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等