事情的起因是今天的日题 1911.最大子序列交替和，我最初的做法是直接找到价格变化中的上升线📈，然后最高点减去最低点，对于边界的处理只需要首尾各加入一个 $0$（因为价格大于 $0$），这个题本就这么做完了。

# Python3
class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        nums.append(0)

        # 两个数维护上升趋势
        n = len(nums)
        res = 0
        sm, bg = 0, 0
        for i in range(n):
            curr = nums[i]
            if curr > bg:
                bg = curr
            else:
                # if bg != sm:    # 可以省略
                res += bg - sm  
                sm = bg = curr

        return res

后来在评论区发现其实这个问题有一个一模一样的题目 122.买卖股票的最佳时机 II。
打开后发现确实几乎是一模一样的题目，解法甚至可以直接用，唯一的区别就是 sm 变量初始值应该设置为第一个价格（因为需要先买入才能有收益）。

// cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        prices.push_back(0);

        int sm = prices[0], bg = prices[0];
        int res = 0;
        for (int p: prices) {
            if (p > bg) bg = p;
            else {
                res += bg - sm;
                bg = sm = p;
            }
        }

        return res;
    }
};

后来发现灵神采用的方法其实是动态规划，并不是这种直接找高低差的方法，而且这么做，经过优化后时间/空间复杂度和我的做法是一致的，而 DP 的做法胜在思路清晰，而且针对于其他变种更为通用，于是在这里做一个学习记录。

动态规划 + 记忆化搜索

首先，不加优化的，我们从后往前思考，一个 启发思路 是：每一天的收益，就是 前一天的收益 + 当天的利润，而 当天的利润 可以是 0、-prices[i]、prices[i]，分别对应什么也不做，买入当天的股票以及卖出持有的股票。

其 递归边界 就是状态开始的时候，如果没有持有股票，即收益为 0，若持有股票，即是一种不合法的状态，初始化为 -inf 即可。

由于最后一天如果我们持有股票，肯定会浪费，dfs(n - 1, 1) 一定小于 dfs(n - 1, 0)，于是我们需要的结果即为 dfs(n - 1, 0)。

# py
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(day: int, hold: bool) -> int:
            if day < 0:
                return 0 if not hold else -inf
            
            if hold:
                return max(dfs(day - 1, True), dfs(day - 1, False) - prices[day])
            return max(dfs(day - 1, False), dfs(day - 1, True) + prices[day])
        
        return dfs(n - 1, False)

去掉递归中 “递” 得部分，我们就可以改为递推：

# py
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        f = [[0] * 2 for _ in range(n + 1)]
        f[0][0] = 0
        f[0][1] = -inf
        
        for day in range(n):
            f[day + 1][1] = max(f[day][1], f[day][0] - prices[day])
            f[day + 1][0] = max(f[day][0], f[day][1] + prices[day])
    
        return f[n][0]

接下来将空间加以优化，就得到了时间复杂度 $O(n)$、空间复杂度 $O(1)$ 的算法：

# py
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        f0 = 0
        f1 = -inf
        
        for day in range(n):
            new_f1 = max(f1, f0 - prices[day])
            f0 = max(f0, f1 + prices[day])
            f1 = new_f1
    
        return f0

变体

接下来考虑到如果卖出股票后有冷冻期或是交易次数有限制的变体问题，我在这里直接贴上代码以及灵神的视频讲解。

309.最佳买卖股票时机含冷冻期

// java
class Solution {
    int [] prices;
    int[][] mem;

    public int maxProfit(int[] prices) {
        this.prices = prices;
        int n = prices.length;
        mem = new int[n][2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(mem[i], -1);
        }
        return dfs(n - 1, 0);
    }
    
    int dfs(int day, int hold) {
        if (day < 0) {
            if (hold == 1) return Integer.MIN_VALUE;
            return 0;
        }

        if (mem[day][hold] != -1) return mem[day][hold];

        if (hold == 1) {
            int tmp = Math.max(dfs(day - 1, 1), dfs(day - 2, 0) - prices[day]); // 唯一的区别就是状态转换在考虑卖出时需要考虑 2 天前，即 day - 2
            mem[day][hold] = tmp;
            return tmp;
        }
        int tmp = Math.max(dfs(day - 1, 0), dfs(day - 1, 1) + prices[day]);
        mem[day][hold] = tmp;
        return tmp;
    }
}

188.买卖股票的最佳时机 IV
最多交易 k 次的情况，需要加入记录交易次数的状态。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(i, j, hold):
            if j < 0:
                return -inf
            if i < 0:
                return -inf if hold else 0
            if hold:
                return max(dfs(i - 1, j, True), dfs(i - 1, j - 1, False) - prices[i])
            return max(dfs(i - 1, j, False), dfs(i - 1, j, True) + prices[i])
        return dfs(n - 1, k, False)

附

121.买卖股票的最佳时机

最原始的题目，不需要使用 DP，跟本专题联系不大。

// java
class Solution {
    public int maxProfit(int[] prices) {
        int metMin = Integer.MAX_VALUE;
        int res = 0;
        for (int price: prices) {
            res = Math.max(res, price - metMin);
            metMin = Math.min(metMin, price);
        }
        return res;
    }
}