买卖股票的最佳时机II

Leetcode Link: 122. 买卖股票的最佳时机 II - 力扣（LeetCode）

题目

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

解法一

思路：贪心，分解成每天都操作一次

本题哪里有坑？

1. 没说能买卖多少次，实际上能买卖很多次
2. 没说能不能当天卖了当天再买，实际上可以。

那么这道题就好说了，你想赚钱，就只要是正利润就买卖，利润为负就不买

由于本题没说卖了之后当天不能立刻买，所以这种情况是可以的。因此在本题的背景下，持有股票三天，等价于三天每天都买当天的股票，卖出昨天的股票！因此可以分解成每天的操作上，这就是需要贪心的地方，只要保证相邻天的买卖操作是正利润就行了！负利润就不买

开始的想法

我开始以为解法是相邻天数价格变化差，然后求最大子序列和（就是最大子序和这道题）… 这种答案是只能买卖一次，而本题没有这种限制，恰好我return 这个diff vector发现了这个坑…

题解：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(1, len(prices)):
            if (prices[i] - prices[i-1]) > 0:
                res += prices[i] - prices[i-1]
        return res

解法二

从暴力递归到动态规划

暴力递归

由于本题中只能持有一个股票，所以需要一个参数来表明当前持股的状态，只有根据当前的持股状态，才能进行情况讨论。

在未持股时，可以选择在第 idx 天买或者不买

在持股时，可以选择在第 idx 天卖或者不卖。

要将利润的计算绕一个弯，输入的参数中不能有 cost，否则改写成 dp 的时候很难确定 dp 数组的大小¹

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return self.process(prices, 0, 0)
 
	# 返回 [idx..n]的最大利润
    def process(self, prices, idx, state):
	    # base case
        if idx == len(prices):
            return 0
 
        if state == 0:  # 未持有股票
            p1 = self.process(prices, idx+1, 0) # 不买
            p2 = self.process(prices, idx+1, 1) - prices[idx]  # 买
        else:
            p1 = self.process(prices, idx+1, 1) # 不卖
            p2 = self.process(prices, idx+1, 0) + prices[idx] # 卖
        return max(p1, p2)

记忆化搜索

• 直接使用 functools.lru_cache()

在类方法中使用该装饰器，不能传入列表参数，需要将其指定为类变量，避免传入。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        self.prices = prices
        return self.process( 0, 0)
 
	# 返回 [idx..n]的最大利润
    @functools.lru_cache(None) # 或者 @cache 没括号，建议。
    def process(self, idx, state):
	    # base case
        if idx == len(self.prices):
            return 0
 
        if state == 0:  # 未持有股票
            p1 = self.process(idx+1, 0) # 不买
            p2 = self.process(idx+1, 1) - self.prices[idx]  # 买
        else:
            p1 = self.process(idx+1, 1) # 不卖
            p2 = self.process(idx+1, 0) + self.prices[idx] # 卖
        return max(p1, p2)

或者在主函数中直接定义新的函数

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        @functools.lru_cache(None)
        def process(idx, state):
            if idx == len(prices):
                return 0
 
            if state == 0:
                p1 = process( idx+1, 0)
                p2 = process( idx+1, 1) - prices[idx]
            else:
                p1 = process( idx+1, 1)
                p2 = process( idx+1, 0) + prices[idx]
            return max(p1, p2)
        return process( 0, 0)

动态规划

直接改就行，2 维 dp，不难初始化为0的话可以省略哦

注意dp的依赖以及遍历方向~

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #[i, state] 当前层依赖下一层
        dp = [[0 for _ in range(2)] for _ in range(len(prices)+1)]
        for i in range(len(prices)-1, -1, -1):
            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[0][0]

动态规划（状态压缩）

通过观察，发现只和当前层和下一层有关，所以必然可以做状态压缩

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #[i, state] 当前层依赖下一层
        dp_cur =[0 for _ in range(2)] # 当前层
        dp_last = [0 for _ in range(2)] # 上一层
        for i in range(len(prices)-1, -1, -1):
            dp_cur[0] = max(dp_last[0], dp_last[1]-prices[i])
            dp_cur[1] = max(dp_last[1], dp_last[0]+prices[i])
            dp_cur, dp_last = dp_last, dp_cur
        return dp_last[0]

启发和联系

Footnotes

1. 可以参考买卖股票的最佳时机III，有同样的问题，但是解释更加详细。 ↩