算法练习Day50|● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV

这篇具有很好参考价值的文章主要介绍了算法练习Day50|● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode:123.买卖股票的最佳时机III

123. 买卖股票的最佳时机 III - 力扣(LeetCode)

1.思路

将两次买入卖出转化为是否持有的状态,当天可进行两次买卖,故每天买卖有四种状态,四种状态包含了当天不买不卖的状态。

2.代码实现
 1class Solution {
 2    public int maxProfit(int[] prices) {
 3
 4        // 根据买入卖出定义多种状态:0表示不操作,1表示第一次持有,2表示第一次不持有,3表示第二次持有,4表示第2次不持有
 5        int[][] dp = new int[prices.length][5];
 6        dp[0][0] = 0;
 7        dp[0][1] = -prices[0];
 8        dp[0][2] = 0;
 9        dp[0][3] = -prices[0];
10        dp[0][4] = 0;
11
12        for (int i = 1; i < prices.length; i++) {
13            // 第一次持有,前一天就持有 或 第i天买入持有
14            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
15            // 第一次不持有,前一天不持有 或 第i天不持有
16            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
17            // 第二次持有,前一天第二次持有 或 前一天不持有第i天持有
18            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
19            // 第二次不持有,前一天第二次不持有 或前一天第二次持有第i天卖出
20            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
21        }
22        return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][4]);
23    }
24}
25
3.复杂度分析

时间复杂度:O(n).
空间复杂度:O(1).

LeetCode:188.买卖股票的最佳时机IV 

188. 买卖股票的最佳时机 IV - 力扣(LeetCode)

1.思路

在上一题的基础上,将第i天是否持有股票或不持有和第几次持有或不持有股票作为一个循环体进行i天,每天k次的循环遍历,最终输出结果即可。

2.代码实现
 1class Solution {
 2    public int maxProfit(int k, int[] prices) {
 3
 4        // 定义dp[][][] 数组,[天数][交易次数][是否持有股票]
 5        int len = prices.length;
 6        int[][][] dp = new int[len][k + 1][2];
 7
 8        // 初始化dp数组
 9        // 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润
10        for (int i = 0; i <= k; i++) {
11            dp[0][i][1] = -prices[0];
12        }
13
14        for (int i = 1; i < len; i++) {
15            for (int j = 1; j <= k; j++) {
16                // 0 表示不持有股票
17                // 1 表示持有股票
18                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
19                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
20            }
21        }
22        return dp[len - 1][k][0];
23    }
24}
25
3.复杂度分析

时间复杂度:O(nk). 空间复杂度:O(nk).文章来源地址https://www.toymoban.com/news/detail-656467.html

到了这里,关于算法练习Day50|● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 123. 买卖股票的最佳时机 III

    123. 买卖股票的最佳时机 III - 力扣(LeetCode) 给定一个数组,它的第   i  个元素是一支给定的股票在第  i   天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成  两笔  交易。 注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

    2024年02月07日
    浏览(43)
  • 刷题第四十二天 123. 买卖股票的最佳时机Ⅲ 188. 买卖股票的最佳时机Ⅳ

    和前一题的限制在于只能买卖两次,所以dp数组多定义一个状态,分别表示第一次持有 第一次不持有和第二次持有 第二次不持有,然后进行更新。 注意初始化的时候 第一次持有和第二次持有都需要默认0-prices[0] 和前一题的差别就是可以多次买卖,所以定义一个三维数组,表

    2024年02月05日
    浏览(47)
  • 123.买卖股票的最佳时机II

    123.买卖股票的最佳时机II https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

    2024年02月20日
    浏览(37)
  • 算法刷题Day 51 最佳买卖股票时机含冷冻期+买卖股票的最佳时期含手续费

    关键是要画出状态转移图 然后根据状态转移图来写状态转移方程 这道题其实就是在买卖股票II的基础上加入一点变化而已,代码框架还是那个框架。

    2024年02月15日
    浏览(44)
  • 【学会动态规划】买卖股票的最佳时机 III(17)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:123. 买卖股票的最佳时机 II

    2024年02月13日
    浏览(52)
  • DAY36:贪心算法(三)最大子数组和+买卖股票最佳时机

    给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 10^5 -10^4 = nums[i] = 10^4 枚举思路 本题的暴力解法就是两个for循环,一个for循环遍

    2024年02月12日
    浏览(54)
  • Day32 贪心算法 part02 122. 买卖股票的最佳时机 II 55. 跳跃游戏 45. 跳跃游戏 II

    思路:计算每天的利润,利润如果为正,加到结果中去

    2024年01月19日
    浏览(44)
  • 【Day53】代码随想录之动态规划part10——买卖股票的最佳时机、买卖股票的最佳时机II

    昨天已经把打家劫舍的问题解决了,最后一个题目涉及到树形dp比较难(等到二刷的时候再重点看下),今天的任务是解决股票问题。 今日任务: 121.买卖股票的最佳时机 122.买卖股票的最佳时机II Leetcode题目:【121.买卖股票的最佳时机】 因为此题中买卖股票只能买卖一次。

    2024年03月15日
    浏览(96)
  • 算法刷题|121.买卖股票的最佳时机、122.买卖股票的最佳时机Ⅱ

    题目:给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获

    2023年04月26日
    浏览(43)
  • DAY55:动态规划(买卖股票的最佳时机3)

    这道题比上面状态更多,是因为卖出股票后,你无法在第二天买入股票 (即冷冻期为1天)。 状态 状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有) 不持有股票状态,这里就有两种卖出股票状态 状态二:保持卖出股票的状态(两天前

    2024年02月22日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包