当前位置：首页 > article >正文

算法随想录第五十一天打卡|309.最佳买卖股票时机含冷冻期， 714.买卖股票的最佳时机含手续费 ,总结

article 2024/11/15 8:46:49

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

本题加了一个冷冻期，状态就多了，有点难度，大家要把各个状态分清，思路才能清晰

视频讲解：动态规划来决定最佳时机，这次有冷冻期！| LeetCode：309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili

代码随想录

思路

还是用的之前的方法，就是多加了个冷冻期。

class Solution(object):
    def maxProfit(self, prices):
        length=len(prices)
        if length%3==1:
            case=length
            deg=length//3
        elif length%3==0:
            case=length+1
            deg=length//3
        else:
            case=length+1
            deg=length//3+1
        #deg表示要初始化的数量
        #case表示最大有几种情况
        dp=[[0]*case for _ in range(len(prices))]
        i=1  #表示初始化的起始量
        while deg!=0:  #进行初始化
            dp[0][i]=-prices[0]
            i+=3
            deg-=1
        for i in range(1,length):
            dp[i][0]=dp[i-1][0]
            for j in range(1,case):
                if j%3==1:  #表示持有的时候
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
                elif j%3==2:  #表示未持有的时候
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])
                else:  #表示冷冻期的时候
                    dp[i][j]=dp[i-1][j-1]
        return max(dp[-1])

答案

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        dp = [[0] * 4 for _ in range(n)]  # 创建动态规划数组，4个状态分别表示持有股票、不持有股票且处于冷冻期、不持有股票且不处于冷冻期、不持有股票且当天卖出后处于冷冻期
        dp[0][0] = -prices[0]  # 初始状态：第一天持有股票的最大利润为买入股票的价格
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])  # 当前持有股票的最大利润等于前一天持有股票的最大利润或者前一天不持有股票且不处于冷冻期的最大利润减去当前股票的价格
            dp[i][1] = max(dp[i-1][1], dp[i-1][3])  # 当前不持有股票且处于冷冻期的最大利润等于前一天持有股票的最大利润加上当前股票的价格
            dp[i][2] = dp[i-1][0] + prices[i]  # 当前不持有股票且不处于冷冻期的最大利润等于前一天不持有股票的最大利润或者前一天处于冷冻期的最大利润
            dp[i][3] = dp[i-1][2]  # 当前不持有股票且当天卖出后处于冷冻期的最大利润等于前一天不持有股票且不处于冷冻期的最大利润
        return max(dp[n-1][3], dp[n-1][1], dp[n-1][2])  # 返回最后一天不持有股票的最大利润

总结

虽然说我觉得能写出来就已经不错了，但是他的时间和空间都要的很多。答案只有5种状态，他没有算次数，所以要更简单一些。我的可以成为暴力法了。

714.买卖股票的最佳时机含手续费

相对122.买卖股票的最佳时机II ，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的，可以尝试自己做一做。

视频讲解：动态规划来决定最佳时机，这次含手续费！| LeetCode：714.买卖股票的最佳时机含手续费_哔哩哔哩_bilibili

代码随想录

class Solution(object):
    def maxProfit(self, prices, fee):
        #0.表示持有股票的时候
        #1.表示没有持有股票的时候
        dp=[[0]*2 for _ in range(len(prices))]
        dp[0][0]=-prices[0]
        for i in range(1,len(prices)):
            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]-fee)
        return dp[-1][1]