首页 > 其他分享 >力扣309.买卖股票的最佳时机含冷冻期

力扣309.买卖股票的最佳时机含冷冻期

时间:2024-05-06 16:24:36浏览次数:25  
标签:持股 309 持有 力扣 int 最佳时机 prices 卖出 dp

题目

给定一个整数数组prices,其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

解题思路

​ 动态规划——这题必须膜拜大神

正文:
因为当天卖出股票实际上也是属于“不持有”的状态,那么第i天如果不持有,那这个“不持有”就有了两种状态:1.本来就不持有,指不是因为当天卖出了才不持有的;2.第i天因为卖出了股票才变得不持有

而持有股票依旧只有一种状态

所以对于每一天i,都有可能是三种状态:
0.不持股且当天没卖出,定义其最大收益dp[i][0];
1.持股,定义其最大收益dp[i][1]
2.不持股且当天卖出了,定义其最大收益dp[i][2]

初始化:
dp[0][0]=0;//本来就不持有,啥也没干
dp[0][1]=-1*prices[0];//第0天只买入
dp[0][2]=0;//可以理解成第0天买入又卖出,那么第0天就是“不持股且当天卖出了”这个状态了,其收益为0,所以初始化为0是合理的

重头戏:

一、第i天不持股且没卖出的状态dp[i][0],也就是我没有股票,而且还不是因为我卖了它才没有的,那换句话说是从i-1天到第i天转移时,它压根就没给我股票!所以i-1天一定也是不持有,那就是不持有的两种可能:i-1天不持股且当天没有卖出dp[i-1][0];i-1天不持股但是当天卖出去了dp[i-1][2]
所以: dp[i][0]=max(dp[i-1][0],dp[i-1][2])

二、第i天持股dp[i][1],今天我持股,来自两种可能:
1、要么是昨天我就持股,今天继承昨天的,也就是dp[i-1][1],这种可能很好理解;
2、要么:是昨天我不持股,今天我买入的,但前提是昨天我一定没卖!因为如果昨天我卖了,那么今天我不能交易!也就是题目中所谓“冷冻期”的含义,只有昨天是“不持股且当天没卖出”这个状态,我今天才能买入!所以是dp[i-1][0]-p[i]
所以: dp[i][1]=max(dp[i-1][1],dp[i-1][0]-p[i])

三、i天不持股且当天卖出了,这种就简单了,那就是说昨天我一定是持股的,要不然我今天拿什么卖啊,而持股只有一种状态,昨天持股的收益加上今天卖出得到的新收益,就是dp[i-1][1]+p[i]
所以:dp[i][2]=dp[i-1][1]+p[i]

总结:最后一天的最大收益有两种可能,而且一定是“不持有”状态下的两种可能,把这两种“不持有”比较一下大小,返回即可

代码

class Solution {
    public int maxProfit(int[] prices) {
        int length=prices.length;

        if(length==1){
            return 0;
        }

        int[][] dp=new int[length][3];

        //不持有且当天没卖出
        dp[0][0]=0;
        //持有
        dp[0][1]=-1*prices[0];
        //不持有且当天卖出
        dp[0][2]=0;

        for(int i=1;i<length;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2]=dp[i-1][1]+prices[i];
        }

        return Math.max(dp[length-1][0],dp[length-1][2]);
    }
}

标签:持股,309,持有,力扣,int,最佳时机,prices,卖出,dp
From: https://www.cnblogs.com/always-uie/p/18175228

相关文章

  • 力扣1235 2024.5.4
    原题网址:https://leetcode.cn/problems/maximum-profit-in-job-scheduling/submissions/529098063/个人难度评价:1600分析:一眼DP,考虑DP顺序,DP递推式与边界十分类似背包,记i为第i段时间,显然有dp[i]=max(dp[i-1],dp[b[i]]+p[i])由此得出递推顺序为按结束时间为第一关键字升序递推......
  • 力扣-304. 二维区域和检索
    1.题目题目地址(304.二维区域和检索-矩阵不可变-力扣(LeetCode))https://leetcode.cn/problems/range-sum-query-2d-immutable/题目描述给定一个二维矩阵matrix,以下类型的多个请求:计算其子矩形范围内元素的总和,该子矩阵的左上角为(row1, col1),右下角为(row2, co......
  • 力扣-303. 区域和检索
    1.题目题目地址(303.区域和检索-数组不可变-力扣(LeetCode))https://leetcode.cn/problems/range-sum-query-immutable/题目描述给定一个整数数组 nums,处理以下类型的多个查询:计算索引 left 和 right (包含left和right)之间的nums元素的和,其中 left<=righ......
  • 力扣198.打家劫舍*
    引言在做动态规划专题的过程中发现打家劫舍是一个十分经典的动态规划类型题,之后的好多题都有这道题的影子,比如我下一篇准备整理的740.删除并获得点数,弄明白打家劫舍真的可以算是动态规划入门了(所以这个动态规划门槛也太高了吧,我的脑子,我的脑子啊)题目你是一个专业的小偷,计划偷窃......
  • 力扣740.删除并获得点数
    题目给你一个整数数组nums,你可以对它进行一些操作。每次操作中,选择任意一个nums[i],删除它并获得nums[i]的点数。之后,你必须删除所有等于nums[i]-1和nums[i]+1的元素。开始你拥有0个点数。返回你能通过这些操作获得的最大点数。解题思路​ 动态规划----打家......
  • 力扣746.使用最小花费爬楼梯
    题目给你一个整数数组cost,其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费解题思路​ 动态规划1.首先需要明确,先支付......
  • 力扣-430. 扁平化多级双向链表
    1.题目题目地址(430.扁平化多级双向链表-力扣(LeetCode))https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/题目描述你会得到一个双链表,其中包含的节点有一个下一个指针、一个前一个指针和一个额外的子指针。这个子指针可能指向一个单独的双向链表,也......
  • 力扣-82. 删除排序链表中的重复元素
    1.题目题目地址(82.删除排序链表中的重复元素II-力扣(LeetCode))https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/题目描述给定一个已排序的链表的头 head, 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回已排序的链表 。 示例1:......
  • 力扣-83. 删除排序链表中的重复元素
    1.题目题目地址(83.删除排序链表中的重复元素-力扣(LeetCode))https://leetcode.cn/problems/remove-duplicates-from-sorted-list/题目描述给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回已排序的链表 。 示例1:输入:head=[1,1......
  • 【DP】买卖股票的最佳时机III
    题源-之前都是数组存,然后转移状态,这次是直接四个变量,非常神奇-在该问题中,定义了五种状态,分别是:未进行过任何操作、只进行过一次买操作、进行了一次买操作和一次卖操作(完成了一笔交易)、在完成了一笔交易的前提下进行了第二次买操作以及完成了全部两笔交易。-然后,通过状态转移方......