分析:
初看题目还是有点难
开始状态准备建在第i天买入还是抛出股票,这种状态建立出来不能状态转移
翻阅了一下题解,再次重新建立状态,在第i天是否持有股票
dp[i][j]表示到第i天所能获得的最大利润
dp[i][0]是在第i天不持有股票,要么在当天抛出股票,要么状态跟上一天一样什么也不做
dp[i][1]是在第i天持有股票,要么在当天购入,要么就是维持上一天的状态,依然持有股票
所以得转移:
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
代码:
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ # dp[i][j]表示在第i天能获取的最大利润 # dp[i][0]表示在第i天不持有股票,dp[i][1]表示持有股票 n = len(prices) dp = [[0]*2 for _ in range(n)] dp[0][1] = -prices[0] for i in range(1, n): dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) return dp[n - 1][0]