买卖股票的最好时机(二)

class Solution:
    def maxProfit(self , prices ):
        # write code here
        # dp[i][j]定义为前i天在状态j（0/1 -> 不持股/持股）下的最高收益
        length = len(prices)
        dp = [[0]*2 for _ in range(length+1)]
        # basecase 第0天持股不可能发生
        dp[0][1] = -float('INF')
        for i in range(1,length+1):
            # 对应接下来的每一天,可能会有两种最终状态(持股/不持股)
            # 若到第i天不持股,有两种可能
            # 1.昨天不持股->今天依旧不持股  2.昨天持股->今天按当天价格卖出
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i-1])
            # 若到第i天持股,也有两种可能
            # 1.昨天持股->今天依旧持股  2.昨天不持股->今天按当天价格买入股
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i-1])
        # 返回最后一天的最大收益 即不持有股票的状态
        # 因为最后一天肯定是全部股票折现的收益更大
        return dp[length][0]

class Solution:
    def maxProfit(self , prices ):
        # write code here
        length = len(prices)
        dp_i_0 = 0
        dp_i_1 = -float('INF')
        for i in range(1,length+1):
            temp = dp_i_0
            dp_i_0 = max(dp_i_0, dp_i_1+prices[i-1])
            dp_i_1 = max(dp_i_1, temp-prices[i-1])
        # 返回最后一天的最大收益（即不持有股票的状态）
        return dp_i_0