趁热打铁，拿下它的进阶版：LeetCode第122题“买卖股票的最佳时机 II”。

这道题的难度标的是“中等”，但如果昨天已经彻底吃透了121题的动态规划思路，今天这道题其实也就是一层窗户纸的事。

稍微梳理一下题意：给定一个代表每天股票价格的数组，和昨天最大的不同在于，这次可以买卖多次，但是在任何时候手里最多只能持有一股（也就是说必须先卖出才能再买入）。求最后能获取的最大总利润。

拿题目给的例子 [7,1,5,3,6,4] 来说，如果在第2天（价格为1）买入，第3天（价格为5）卖出，赚了4块；紧接着第4天（价格为3）再次买入，第5天（价格为6）卖出，又赚了3块。总利润就是 4 + 3 = 7。

针对这道题，依然有两种非常经典的解法：贪心和动态规划。

贪心思路

因为这次买卖次数没有限制了，那想要利润最大化，最直观的想法就是：我把所有上涨的差价都赚到手，所有下跌的日子我都不参与。

我们可以把整个股票的走势想象成连绵起伏的山峰和山谷。既然可以在同一天卖出再买入，那我就把数组中每一天的价格和前一天的价格做一个对比：
只要今天的价格比昨天高，也就是产生了正利润，那我就假设我昨天买入了，今天卖出了，把这笔利润加到总账里。如果今天的价格比昨天低，那我就当无事发生。

局部最优解就是收集每天的正利润，最后推导出的全局最优解自然就是最大总利润了。

贪心思路的代码极其简单，几行就能搞定。

Java实现（贪心）：

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        // 从第二天开始遍历，和前一天比较
        for (int i = 1; i < prices.length; i++) {
            // 只要有正利润就收下
            if (prices[i] - prices[i - 1] > 0) {
                result += prices[i] - prices[i - 1];
            }
        }
        return result;
    }
}

Python实现（贪心）：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i in range(1, len(prices)):
            # 直接累加所有相邻两天的正向差值
            if prices[i] > prices[i - 1]:
                result += prices[i] - prices[i - 1]
        return result

动态规划思路

虽然贪心算法这回大放异彩，代码短得让人不敢相信这是道“中等”题。但是，昨天我就在日记里提醒过自己：动态规划才是股票系列的万能钥匙。

今天用动规来解，更能体会到这种框架思维的强大。我按照昨天的动规五部曲重新推导了一遍，发现除了递推公式里的一处极小改动，其他竟然完全一样。

1. 确定dp数组以及下标的含义
和昨天一模一样：
dp[i][0] 表示第 i 天持有股票时的最大现金。
dp[i][1] 表示第 i 天不持有股票时的最大现金。

2. 确定递推公式（重点来了！）
先看 dp[i][1]（不持有股票）：
它的来源和昨天一样，要么是昨天就不持有（dp[i - 1][1]），要么是昨天持有但今天卖了（dp[i - 1][0] + prices[i]）。两者取最大值。这部分没变。

再看 dp[i][0]（持有股票）：
这里就有大文章了。如果第 i 天我手里有股票，要么是昨天就持有着（dp[i - 1][0]），要么是今天刚买入的。
昨天那道题规定只能买卖一次，所以如果今天买入，那么买入前的本金一定是0，买入后的现金就是 -prices[i]。
但是今天这道题允许买卖多次！ 这意味着，如果我今天买入股票，我手里可能是拿着之前某次交易赚到的本金的。换句话说，今天买入股票之前的现金状态，其实就是昨天“不持有股票”的状态 dp[i - 1][1]。
因此，今天买入股票后的现金应该是：dp[i - 1][1] - prices[i]。

两者取最大值，递推公式变成了：dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i])。

3. 初始化和遍历顺序
全部和昨天保持一致。dp[0][0] = -prices[0]，dp[0][1] = 0。从前向后遍历。

一套分析下来，我发现仅仅只是把昨天代码里的 -prices[i] 替换成了 dp[i - 1][1] - prices[i]，这道进阶题就被拿下了。

Java实现（动态规划）：

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int length = prices.length;
        
        int[][] dp = new int[length][2];
        
        // 初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        
        for (int i = 1; i < length; i++) {
            // 核心差别就在这一行：买入股票时，需要加上之前不持有股票时的现金（之前交易的利润）
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // 卖出股票逻辑不变
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        
        return dp[length - 1][1];
    }
}

Python实现（动态规划）：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
            
        length = len(prices)
        dp = [[0] * 2 for _ in range(length)]
        
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        
        for i in range(1, length):
            # 唯一区别：今天买入的话，手里剩下的钱是昨天的利润减去今天的股价
            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[-1][1]

总结体会

写完这两版代码，心里有一种极其舒畅的感觉。

贪心算法确实精妙，像脑筋急转弯，想到了就一击必杀。但是动态规划给我带来的震撼更大。通过严谨的状态定义和状态转移，仅仅改动了一处变量，就把一个“单次交易”的模型无缝拓展成了“无数次交易”的模型。

这也更加坚定了我之前的判断：顺着这套动规状态转移的逻辑去想，后面不管是加手续费，还是加冷冻期，乃至限制最多只能交易K次，无非也就是多定义几个状态而已，核心骨架已经立住了。巩固好这套内功心法，打卡收工。