解题思路1 (动态规划):
-
dp_0[i][k]
: 表示 第i天交易了k次时空仓的累计最大利润
dp_1[i][k]
: 表示 第i天交易了k次时持仓的累计最大利润 -
初始状态:第i天空仓且之前没交易过,由初始状态转移过来,即昨天也空仓,
dp_0[i][0] = dp_0[i-1][0]
-
第一次买入:第i天持仓且之前没交易过,由两个状态转移过来,即昨天空仓,今天买入,或者昨天持仓今天继续持仓:
dp_1[i][0] = max(dp_1[i-1][0], dp_0[i-1][0]-prices[i])
-
第一次卖出:第i天空仓且之前交易过,由两个状态转移过来,即昨天空仓今天继续空仓,或者昨天持仓今天卖出,因为卖出才算完成交易昨天持仓今天卖出,昨天持仓状态的k=0:
dp_0[i][1] = max(dp_0[i-1][1], dp_1[i-1][0]+prices[i])
-
第二次买入 第i天持仓且之前交易过一轮,有两个状态转移过来,即昨天持仓今天继续持仓,或者昨天空仓今天买入,
dp_1[i][1] = max(dp_1[i-1][1], dp_0[i-1][1]-prices[i])
-
第二次卖出 即第i天空仓且k=2,由一个状态转移过来,即昨天空仓,今天继续空仓,或者昨天持仓今天卖出,
dp_0[i][2] = max(dp_0[i-1][2], dp_1[i-1][1]+prices[i])
python3代码如下:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
len1 = len(prices)
max_k = 2
dp_0 = [[0 for _ in range(max_k+1)] for _ in range(len1)]
dp_1 = [[0 for _ in range(max_k+1)] for _ in range(len1)]
dp_0[0][0] = 0
dp_1[0][0] = -prices[0]
dp_0[0][1] = 0 # 第0天空仓且已经交易了1次,不存在该情况
dp_1[0][1] = -prices[0] # 第0天持仓,且交易了一次,即买入,
dp_0[0][2] = 0 # 第0天空仓且已经交易了2次, 不存在该情况
# dp_1[0][2] = -prices[0] # 第0天持仓,且交易了一次,不存在该情况
for i in range(1, len(prices)):
# 初始
dp_0[i][0] = dp_0[i-1][0]
# 第一次买入、第一次卖出
dp_1[i][0] = max(dp_1[i-1][0], dp_0[i-1][0]-prices[i])
dp_0[i][1] = max(dp_0[i-1][1], dp_1[i-1][0]+prices[i])
# 第二次买入、第二次卖出
dp_1[i][1] = max(dp_1[i-1][1], dp_0[i-1][1]-prices[i])
dp_0[i][2] = max(dp_0[i-1][2], dp_1[i-1][1]+prices[i])
return max(dp_0[-1])
网友评论