类似Best Time to Buy and Sell Stock I,给出每个股票每一天的价格prices[i],但每次卖出之后紧邻的一天为cooldown day,不能买入,思路依旧DP
dp[i][0]表示第i天手中未持有股票的情况下最高收益
dp[i][1]表示第i天手中持有股票的情况下的最高收益,初始化该为为不可能到达的极小负数值
状态转移方程:
if i >= 2:
dp[i][1] = max(dp[i - 2][0] - prices[i - 1], dp[i - 1][1])
else:
dp[i][1] = max(dp[i - 1][0] - prices[i - 1], dp[i - 1][1])
dp[i][
0] =
max(dp[i -
1][
0], dp[i -
1][
1] + prices[i -
1])
1 #309
2 #Runtime: 57 ms (Beats 38.83%)
3 #Memory: 14.1 MB (Beats 43.96%)
4
5 class Solution(object):
6 def maxProfit(self, prices):
7 """
8 :type prices: List[int]
9 :rtype: int
10 """
11 dp = [[0, -5000001] for _ in range(len(prices) + 1)]
12 for i in range(1, len(prices) + 1):
13 if i >= 2:
14 dp[i][1] = max(dp[i - 2][0] - prices[i - 1], dp[i - 1][1])
15 else:
16 dp[i][1] = max(dp[i - 1][0] - prices[i - 1], dp[i - 1][1])
17 dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1])
18 return dp[-1][0]