算法随想录第五十天打卡123.买卖股票的最佳时机III ， 188.买卖股票的最佳时机IV

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

这道题一下子就难度上来了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

视频讲解：动态规划，股票至多买卖两次，怎么求？ | LeetCode：123.买卖股票最佳时机III_哔哩哔哩_bilibili

代码随想录

class Solution(object):
    def maxProfit(self, prices):
        if len(prices)==1:
            return 0
        #0.不持有股票
        #1.第一次持有股票
        #2.第一次不持有股票
        #3.第二次持有股票
        #4.第二次不持有股票
        #这里的dp表示在当前状态下所能获得的最大利益
        dp=[[0]*5 for _ in range(len(prices))]
        dp[0][1]=-prices[0]
        dp[0][3]=-prices[0]
        for i in range(1,len(prices)):
            dp[i][0]=dp[i-1][0]
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
            dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i])
            dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i])
            dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i])
        return dp[-1][4]

总结

刚开始还以为会很难，但看了一下答案后发现其实还是上一题的状态法，只是状态变多了，还是要敢于挑战。

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

本题是123.买卖股票的最佳时机III 的进阶版  

视频讲解：动态规划来决定最佳时机，至多可以买卖K次！| LeetCode：188.买卖股票最佳时机4_哔哩哔哩_bilibili

代码随想录

思路

我没有看到k的只是给了的，所以我以为可以无限买卖，所以以prices的长度来判断最大可以有几种情况。

class Solution(object):
    def maxProfit(self, k, prices):
        length=len(prices)
        if length%2==1:
            case=length  #case表示情况数量
        else:
            case=length+1
        dp=[[0]*case for _ in range(length)]

        deg=(case-1)//2
        i=1
        while deg!=0:
            dp[0][i]=-prices[0]
            deg-=1
            i+=2

        for i in range(1,length):
            dp[i][0]=dp[i-1][0]
            for j in range(1,case):
                if j%2==1:
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])
        return dp[-1][-1]
        

改后的

class Solution(object):
    def maxProfit(self, k, prices):
        length=len(prices)
        if length%2==1:
            case=length  #case表示情况数量
        else:
            case=length+1
        if case>k*2+1:  #比较最大情况数量和k谁最大
            case=k*2+1
        dp=[[0]*case for _ in range(length)]

        deg=(case-1)//2  #要遍历的数量
        i=1
        while deg!=0:
            dp[0][i]=-prices[0]
            deg-=1
            i+=2

        for i in range(1,length):
            dp[i][0]=dp[i-1][0]
            for j in range(1,case):
                if j%2==1:
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])
        return dp[-1][-1]

总结

他其实是情况稍微不一样了，所以我改成了如果k大于最大的情况，就用最大的情况，如果没有大于就有k。没有去优化了。