本文共 2541 字，大约阅读时间需要 8 分钟。

今天是最难的股票题了吧。 11.06. 10:50

今天有股票的最大profit = max（昨天有股票的最大收益， 昨天没有邮票的最大收益 - 昨天买一股票的亏损）

class Solution:    def maxProfit(self, k: int, prices: List[int]) -> int:        n = len(prices)        if n == 0: return 0        if k > n / 2:            dp_ik0 = 0            dp_ik1 = -float('inf')            for i in range(0,n):                temp = dp_ik0                dp_ik0 = max(dp_ik0, dp_ik1 + prices[i])                dp_ik1 = max(dp_ik1, temp - prices[i])            return dp_ik0        else:            dp_table = [[[0 for d in range(2)] for k in range(k + 1)]for i in range(n)]            maxk = k             for i in range(0,n):                for k in range(maxk,0,-1): # 注意这个 -1 不然里面的循环都不会进行了, 注意 k in range（k） 下一次k会混乱                    if i == 0:                        dp_table[0][k][0] = 0                        dp_table[0][k][1] = -prices[i]                    else:                        dp_table[i][k][0] = max(dp_table[i-1][k][0], dp_table[i-1][k][1] + prices[i])                        dp_table[i][k][1] = max(dp_table[i-1][k][1], dp_table[i-1][k-1][0] - prices[i])            # print(dp_table)            # print(k)            return dp_table[n-1][maxk][0]

时间维度优化：

此刻的最大收益，之和前一个时间的最大收益有关：

class Solution:    def maxProfit(self, k: int, prices: List[int]) -> int:        n = len(prices)        if n == 0: return 0        if k > n / 2:            dp_ik0 = 0            dp_ik1 = -float('inf')            for i in range(0,n):                temp = dp_ik0                dp_ik0 = max(dp_ik0, dp_ik1 + prices[i])                dp_ik1 = max(dp_ik1, temp - prices[i])            return dp_ik0        else:            # dp_table = [[[0 for d in range(2)] for k in range(k + 1)]for i in range(n)]            # 优化不需要存储 时间i 维度。 当前时刻的最优解只与 前一个时刻有关            dp_table = [[0 for d in range(2)] for k in range(k + 1)]            maxk = k             for i in range(0,n):                for k in range(maxk,0,-1): # 注意这个 -1 不然里面的循环都不会进行了, 注意 k in range（k） 下一次k会混乱                    if i == 0:                        dp_table[k][0] = 0                        dp_table[k][1] = -prices[i]                    else:                        dp_table[k][0] = max(dp_table[k][0], dp_table[k][1] + prices[i])                        dp_table[k][1] = max(dp_table[k][1], dp_table[k-1][0] - prices[i])            return dp_table[maxk][0]

犯错点

• 对于如下语句：
  双重for循环，从第二遍开始 k 就开始 从1 到1 。 不再从2循环到1。这个错误我找了半个小时。。。。

for i in range(0,n):	for k in range(k,0,-1):

• 倒叙循环最后一个 -1 不要忘记了。

转载地址：http://tnywi.baihongyu.com/