LeetCode 121. 买卖股票的最佳时机

LeetCode 121. 买卖股票的最佳时机

尝试一：暴力解决方法

常用两个指针去遍历prices数组，dp[i]用于记录在第i天所获得的最大利润。时间复杂度是O(N^2)，超出时间限制。

Code

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        ## 买入卖出的次数 <= 1

        ## 1. dp数组定义。
        ## dp[i] 表示第i天前所获得的最大利润

        ## 2. dp初始化
        dp = [0] * (len(prices))

        ## 3. 递推公式
        ## 利润： diff = price[j] - price[i]
        ## 第j天的利润大于等第i天利润，那么第j天利润 = 第i天利润 + 第j天价格 - 第i天价格
        ## dp[j] = max(dp[j], dp[i] + prices[j] - prices[i])

        ## 4. 遍历顺序
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                if prices[j] > prices[i]:
                    dp[j] = max(dp[j], dp[i] + prices[j] - prices[i])
        
        ## 5. 打印dp数组
        return max(dp)

动规的思路：

1. dp数组定义：第i天时，我目前的状态有两种，一种是持有股票，另外一种是已卖出股票，因此dp数组是一个二维数组，第一维用来表示天数，第二维用来表示在这一天我目前手头的股票状态。因此，dp[i][0]表示为 天数<= i 时我已购入一只股票， dp[i][1]表示为 天数 <= i 时 我已卖出一只股票后所获得的最大利润。

2. dp数组初始化： 由于递推公式是前面推后面，因此第一个元素需要初始化。

• dp[0][0] = -prices[0]: 第0天持有购买，是消费行为。
• dp[0][1] = 0: 第0天卖出股票没有利润可言。
• 另外，由于dp[i][0]是针对负数求最大化，因此dp数组要用负无穷去初始化，再对特殊值进行初始化。

3. 递推公式：

• dp[i][0]的情况有两种：第i天前已购买(dp[i-1][0]) / 第 i 天时才购买( -prices[i], 负号表示购买，是亏损了这么多钱)，为获得最大利润，我要尽可能以低的价格购入股票，因此dp[i][0] = max(dp[i-1][0], -prices[i])
• 相应地，dp[i][1]的情况也有两种：第i天前已卖出(dp[i-1][1]) / 第 i 天时才卖出（利润 = prices[i] - dp[i-1][0] (第i天前买入的股票才可以在第i天时卖出) ），那最大利润递推公式就是dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]) 。

Code

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        
        # 1. dp数组定义。由于第i天的现有股票有两种状态，一个是已买入，一个是已卖出，因此需要用一个长度为2的数组来表示这种关系
# dp[i][0], 表示第i天已买入股票的状态，这种状态描述了我在第i天前（包括第i天）购入了一只股票，值表示我购入这支股票所花的钱
# dp[i][1], 表示第i天已卖出股票的状态，这种状态描述了我在第i天前（包括第i天）卖出了一只股票，值表示我卖出这支股票所花的钱

        dp = [[-float('inf')] * 2 for _ in range(len(prices))]
        # 2. dp初始化
        dp[0][0] = -prices[0]
        dp[0][1] = 0

        # 3. 递推公式
        # dp[i][0] = max(dp[i-1][0], -prices[i])
        # dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])  # dp[i-1][0]+prices[i]表示第i天卖出时得到的利润

        # 4. 遍历顺序
        for i in range(len(prices)):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])

        # 5. 打印dp数组
        if dp[-1][1] < 0:    ## 表示亏损了，那还不如不买
            return 0
        return dp[-1][1]