题解 | #买卖股票的最好时机#

python版动态规划题解，更改k适用于任意交易次数

class Solution:
    def maxProfit(self,prices):
        #适用于任意交易次数，只用于本题可以将k维去掉
        len_i=len(prices)  #能交易的总天数
        k=1  #允许交易的最大次数
        len_k=k+1  #如果交易一次，k应该有0和1两个值！！！！！！！！
        dp=[[[0]*2 for _ in range(len_k)] for _ in range(len_i)] #dp[交易的第几天][最多交易k次][手里持有或没有持有股票]
        #base case
        #dp[-1][k][0]=0  还没开始交易的最大利润是0
        #dp[-1][k][1]=-float('inf')  还没开始交易手里不可能出现股票
        #dp[i][0][0]=0  不允许交易的话最大利润肯定是0
        #dp[i][0][1]=-float('inf')  不允许交易手中不可能有股票
        #处理basecase
        # i=0的情况
        for k in range(len_k):
            dp[0][k][0]=0
            dp[0][k][1]=-prices[0]
        #k=0的情况
        for i in range(len_i):
            dp[i][0][0]=0
            dp[i][0][1]=-prices[i]

        for i in range(1,len(dp)):
            for k in range(1,len(dp[0])):
                #第i天手里没有股票的最大利润=max(昨天我就没有，昨天我有我卖了)
                dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
                #第i天手里有股票的最大利润=max(昨天我就有，昨天我没有但是我今天买了)
                dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
        print(dp)
        return dp[-1][-1][0]