题解 | #买卖股票的最好时机(一)#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        if len(prices)<2:
            return 0

        dp = [[0]*2]*(len(prices))
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1,len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
            dp[i][1] = max(dp[i-1][1], -prices[i])

        return dp[len(prices)-1][0]

使用动态规划，将某一天i的收益分为持股和不持股dp[i][1] 和 dp[i][0], 第一天不持股的收益为0，持股的收益为-price[0]。因此dp[0][0] = 0, dp[0][1] = -prices[0]。

第i天若不持股，则有两种可能 1.前一天没持股 2.当天刚卖出。因此第i天持股的最大收益为

dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])

第i天若持股，则有两种可能 1.前一天持股 2.当天刚买入。因此第i天持股的最大收益为

dp[i][1] = max(dp[i-1][1], -prices[i])