动态规划：买卖股票最佳时机（含冷冻期与手续费）

以示例 k=2、prices = [3,3,5,0,0,3,1,4] 为例，最终第 7 天（i=7，价格 = 4）：dp[7][4] = 6。验证了代码的通用性。

代码实现

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int len = prices.length;
        // dp[i][j]：第 i 天处于第 j 种状态的最大现金
        // j=0：无操作；j=1：第 1 次持有；j=2：第 1 次卖出；...；j=2m-1：第 m 次持有；j=2m：第 m 次卖出
        int[][] dp = new int[len][2 * k + 1];
        
        // 初始化第 0 天的状态：所有'第 m 次持有'状态初始为 -prices[0]，'卖出'状态默认 0
        for (int i = 1; i <= k; i++) {
            dp[0][2 * i - 1] = -prices[0];
        }
        
        // 外层循环：遍历每一天（从第 1 天开始，依赖前一天状态）
        for (int i = 1; i < len; i++) {
            // 内层循环：遍历每一次交易（从第 1 次到第 k 次）
            for (int j = 1; j <= k; j++) {
                // 计算第 j 次持有的最大现金
                dp[i][2 * j - 1] = Math.max(dp[i-1][2 * j - 1], dp[i-1][2 * j - 2] - prices[i]);
                // 计算第 j 次卖出的最大现金
                dp[i][2 * j] = Math.max(dp[i-1][2 * j], dp[i-1][2 * j - 1] + prices[i]);
            }
        }
        
        return dp[len - 1][2 * k];
    }
}

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

思路分析

第一步：状态定义

需要细化状态以覆盖'冷冻期'约束，定义 dp[i][j] 为第 i 天处于状态 j 时的最大现金，其中 j 分为 3 种状态：

• j=0：第 i 天持有股票；
• j=1：第 i 天不持有股票且处于冷冻期（说明第 i-1 天卖出了股票）；
• j=2：第 i 天不持有股票且不处于冷冻期（当天可以买入）。

第二步：状态转移方程

• 状态 0（持有股票）：dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i])
  • 第 i-1 天就持有股票，第 i 天继续持有；
  • 第 i 天买入股票 → 只能用'第 i-1 天不持有且非冷冻期'的现金买入。
• 状态 1（不持有且冷冻期）：dp[i][1] = dp[i-1][0] + prices[i]
  • 第 i-1 天持有股票，第 i 天卖出 → 卖出后当天进入冷冻期。
• 状态 2（不持有且非冷冻期）：dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2])
  • 第 i-1 天处于冷冻期，第 i 天恢复为非冷冻期；
  • 第 i-1 天本身就不持有且非冷冻期，第 i 天继续保持。

第三步：初始化

• dp[0][0] = -prices[0]：第 0 天买入股票；
• dp[0][1] = 0：第 0 天无法卖出，冷冻期状态初始为 0；
• dp[0][2] = 0：第 0 天不持有股票且非冷冻期。

第四步：遍历顺序

从第 1 天（i=1）遍历到最后一天（i=len-1），保证计算时前一天状态已确定。

第五步：手动模拟

以经典示例 prices = [1,2,3,0,2] 为例，最大利润为 3。逐天计算验证状态转移正确性。

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int len = prices.length;
        // dp[i][0]：第 i 天持有股票的最大现金
        // dp[i][1]：第 i 天不持有股票且处于冷冻期的最大现金
        // dp[i][2]：第 i 天不持有股票且不处于冷冻期的最大现金
        int[][] dp = new int[len][3];
        
        // 初始化第 0 天的状态
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        
        // 遍历天数：从第 1 天到最后一天
        for (int i = 1; i < len; i++) {
            // 状态 0：持有股票
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i]);
            // 状态 1：冷冻期
            dp[i][1] = dp[i-1][0] + prices[i];
            // 状态 2：非冷冻期且不持有
            dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
        }
        
        return Math.max(dp[len-1][1], dp[len-1][2]);
    }
}

买卖股票的最佳时机含手续费

思路分析

第一步：状态定义

数组定义和'无限次交易'版本形式一致，但状态含义因手续费规则有细微调整：

• dp[i][0]：表示第 i 天持有股票时，能获得的最大现金；
• dp[i][1]：表示第 i 天不持有股票时，能获得的最大现金。 核心区别：不持有股票的现金计算需扣除卖出时的手续费。

第二步：状态转移方程

• 持有股票的状态（dp[i][0]）：dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
  • 第 i-1 天就持有股票，第 i 天继续持有；
  • 第 i 天才买入股票：dp[i-1][1] - prices[i]。
• 不持有股票的状态（dp[i][1]）：dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
  • 第 i-1 天就不持有股票，第 i 天继续不持有；
  • 第 i 天卖出股票：dp[i-1][0] + prices[i] - fee（核心差异：扣除手续费 fee）。

第三步：初始化

• dp[0][0] = -prices[0]：第 0 天买入股票；
• dp[0][1] = 0：第 0 天不持有股票。

第四步：遍历顺序

从第 1 天（i=1）遍历到最后一天（i=len-1），保证计算 dp[i] 时 dp[i-1] 已确定。

第五步：手动模拟

以经典示例 prices = [1,3,2,8,4,9]、fee=2 为例，最大利润为 8。逐天计算验证。

代码实现

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int len = prices.length;
        // dp[i][0]：第 i 天持有股票时的最大现金
        // dp[i][1]：第 i 天不持有股票时的最大现金
        int[][] dp = new int[len][2];
        
        // 初始化第 0 天的状态
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        
        // 遍历天数：从第 1 天到最后一天
        for (int i = 1; i < len; i++) {
            // 状态转移 1：第 i 天持有股票的最大现金
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
            // 状态转移 2：第 i 天不持有股票的最大现金（核心差异：卖出扣手续费）
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
        }
        
        return dp[len - 1][1];
    }
}