Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
类似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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理