代码随想录算法训练营第四十八天 | 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]
    }
}
相关文章
|
10天前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
14 3
|
9天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
22天前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
|
15天前
|
缓存 分布式计算 监控
优化算法和代码需要注意什么
【10月更文挑战第20天】优化算法和代码需要注意什么
15 0
|
16天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
2天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
3天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
2天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。
|
2天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
14 3