股票问题 (Stock Problems)

[!abstract] 股票系列是 DP 中的经典问题，通过设置不同状态来建模。

---

问题总览

题目	交易次数	冷冻期	手续费
**买卖股票最佳时机**	1次	无	无
**买卖股票最佳时机II**	无限次	无	无
**买卖股票最佳时机III**	2次	无	无
**买卖股票最佳时机IV**	k次	无	无
**最佳买卖股票时机含冷冻期**	无限次	有	无
**买卖股票含手续费**	无限次	无	有

---

1. 买卖股票最佳时机 I

问题

• 只能交易一次（买一次，卖一次），最大利润

// 方法1: 暴力 O(n²)
function maxProfit1(prices: number[]): number {
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      max = Math.max(max, prices[j] - prices[i]);
    }
  }
  return max;
}

// 方法2: 一次遍历 O(n)
function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }

  return maxProfit;
}

// 方法3: DP
function maxProfitDP(prices: number[]): number {
  // dp[i] = 第 i 天不持有股票的最大利润
  // 但我们可以优化到 O(1) 空间

  let dp0 = 0;      // 不持有
  let dp1 = -Infinity; // 持有

  for (const price of prices) {
    dp0 = Math.max(dp0, dp1 + price);  // 卖出
    dp1 = Math.max(dp1, -price);       // 买入
  }

  return dp0;
}

---

2. 买卖股票最佳时机 II

问题

• 可以交易无限次，但每天只能买或卖之一

function maxProfitII(prices: number[]): number {
  let profit = 0;

  for (let i = 1; i < prices.length; i++) {
    // 只要明天比今天高，今天买明天卖
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }

  return profit;
}

// DP 解法
function maxProfitII_DP(prices: number[]): number {
  // dp[i][0] = 第 i 天不持有股票的最大利润
  // dp[i][1] = 第 i 天持有股票的最大利润

  let dp0 = 0;        // 不持有
  let dp1 = -Infinity; // 持有

  for (const price of prices) {
    const newDp0 = Math.max(dp0, dp1 + price);
    const newDp1 = Math.max(dp1, dp0 - price);
    dp0 = newDp0;
    dp1 = newDp1;
  }

  return dp0;
}

---

3. 买卖股票最佳时机 III

问题

• 最多交易 2 次，不能同时持有多股

function maxProfitIII(prices: number[]): number {
  const n = prices.length;
  if (n === 0) return 0;

  // dp[i][j] = 第 i 天，交易 j 次后的最大利润
  // j = 0,1,2,3,4 (0:未买, 1:买1次, 2:卖1次, 3:买2次, 4:卖2次)
  const dp = Array.from({ length: n }, () => Array(5).fill(0));

  // 初始化第一天
  dp[0][1] = -prices[0];
  dp[0][3] = -prices[0];

  for (let i = 1; i < n; i++) {
    dp[i][0] = 0;
    dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
    dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
    dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
    dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
  }

  return dp[n-1][4];
}

// ✅ 空间优化
function maxProfitIII_Optimized(prices: number[]): number {
  let buy1 = -prices[0], sell1 = 0;
  let buy2 = -prices[0], sell2 = 0;

  for (let i = 1; i < prices.length; i++) {
    buy1 = Math.max(buy1, -prices[i]);
    sell1 = Math.max(sell1, buy1 + prices[i]);
    buy2 = Math.max(buy2, sell1 - prices[i]);
    sell2 = Math.max(sell2, buy2 + prices[i]);
  }

  return sell2;
}

---

4. 买卖股票最佳时机 IV

问题

• 最多交易 k 次

function maxProfitIV(k: number, prices: number[]): number {
  const n = prices.length;
  if (n === 0 || k === 0) return 0;

  // 奇数位: buy, 偶数位: sell (从0开始)
  const dp = Array(n).fill(0).map(() => Array(2 * k + 1).fill(0));

  // 初始化所有买入状态
  for (let j = 1; j < 2 * k; j += 2) {
    dp[0][j] = -prices[0];
  }

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < 2 * k; j += 2) {
      dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]);   // buy
      dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]); // sell
    }
  }

  return dp[n-1][2 * k];
}

---

5. 含冷冻期

问题

-卖出后有一天冷冻期，不能买入

function maxProfitWithCooldown(prices: number[]): number {
  const n = prices.length;
  if (n === 0) return 0;

  // dp[i][0] = 第 i 天不持有
  // dp[i][1] = 第 i 天持有
  // dp[i][2] = 第 i 天是冷冻期

  const dp = Array.from({ length: n }, () => Array(3).fill(0));
  dp[0][1] = -prices[0];

  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]); // 保持不持有
    dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); // 买入
    dp[i][2] = dp[i-1][1] + prices[i]; // 冷冻期（今天卖了）
  }

  return Math.max(dp[n-1][0], dp[n-1][2]);
}

// ✅ 空间优化
function maxProfitWithCooldown_Optimized(prices: number[]): number {
  let sold = 0, hold = -prices[0], rest = 0;

  for (let i = 1; i < prices.length; i++) {
    const prevSold = sold;
    sold = hold + prices[i];
    hold = Math.max(hold, rest - prices[i]);
    rest = Math.max(rest, prevSold);
  }

  return Math.max(sold, rest);
}

---

6. 含手续费

function maxProfitWithFee(prices: number[], fee: number): number {
  let hold = -prices[0];
  let cash = 0;

  for (let i = 1; i < prices.length; i++) {
    hold = Math.max(hold, cash - prices[i]);
    cash = Math.max(cash, hold + prices[i] - fee);
  }

  return cash;
}

---

状态转移总结

状态	持有	不持有	冷冻期
hold	max(hold, cash-price)	-	-
cash	max(cash, hold+price-fee)	rest	-
rest	-	max(rest, prevCash)	hold+price

---

7. 股票问题统一模板

问题分类与状态数

问题	状态数	状态定义
买卖股票 I	2	不持有, 持有
买卖股票 II	2	不持有, 持有
买卖股票 III	4	buy1, sell1, buy2, sell2
买卖股票 k次	2k	buy_i, sell_i (i=1..k)
含冷冻期	3	不持有, 持有, 冷冻期
含手续费	2	不持有, 持有

统一代码模板

// 通用股票 DP 框架
function stockTemplate(
  prices: number[],
  options: {
    maxTrade?: number;    // 最大交易次数 (默认无限)
    cooldown?: number;    // 冷冻期天数 (默认0)
    fee?: number;         // 手续费 (默认0)
  } = {}
): number {
  const { maxTrade = Infinity, cooldown = 0, fee = 0 } = options;
  const n = prices.length;
  if (n === 0) return 0;

  // 状态定义
  // buy[i] = 第 i 次买入后的最大收益
  // sell[i] = 第 i 次卖出后的最大收益

  const maxK = Math.min(maxTrade, Math.ceil(n / 2));
  const buy = Array(maxK + 1).fill(-Infinity);
  const sell = Array(maxK + 1).fill(0);

  // 初始化第一次买入
  buy[1] = -prices[0];

  for (let i = 1; i < n; i++) {
    const price = prices[i];

    // 更新买入状态
    for (let k = 1; k <= maxK; k++) {
      buy[k] = Math.max(buy[k], sell[k - 1] - price);
    }

    // 更新卖出状态
    for (let k = 1; k <= maxK; k++) {
      sell[k] = Math.max(sell[k], buy[k] + price - fee);
    }
  }

  return sell[maxK];
}

状态机可视化

普通股票:
┌─────────────────────────────────────────┐
│                                         │
│   ┌─────┐    买(-price)    ┌─────┐      │
│   │ 不  │ ◄───────────────► │ 持  │      │
│   │持有 │                  │ 有  │      │
│   └──┬──┘                  └──┬──┘      │
│      │        卖(+price)      │         │
│      └────────────────────────┘         │
│                                         │
└─────────────────────────────────────────┘

含冷冻期:
┌─────────────────────────────────────────┐
│                                         │
│   ┌─────┐    买    ┌─────┐              │
│   │ 不  │ ◄───────►│ 持  │──┐           │
│   │持有 │          └──┬──┘  │ 卖(+price) │
│   └──┬──┘             │     ▼           │
│      ▲                │    ┌─────┐      │
│      │                │    │冷冻 │      │
│      └────────────────┴────│期   │      │
│                             └──┬──┘      │
│                                │ 一天后  │
│                                ▼         │
│                              不持有      │
└─────────────────────────────────────────┘

含手续费:
┌─────────────────────────────────────────┐
│                                         │
│   ┌─────┐    买(-price)    ┌─────┐      │
│   │ 不  │ ◄───────────────► │ 持  │      │
│   │持有 │                  │ 有  │      │
│   └──┬──┘                  └──┬──┘      │
│      │    卖(+price-fee)     │         │
│      └────────────────────────┘         │
│        ▲                                │
│        │ 每次卖出扣手续费                │
└─────────────────────────────────────────┘

---

8. 股票问题进阶变体

变体1: 买卖股票的最佳时机（含手续费，可交易无限次）

// 方法1: 朴素 DP
function maxProfitWithFeeDP(prices: number[], fee: number): number {
  const n = prices.length;
  const dp = Array.from({ length: n }, () => [0, -prices[0]]);

  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  }

  return dp[n - 1][0];
}

// 方法2: 空间优化
function maxProfitWithFeeOptimized(prices: number[], fee: number): number {
  let cash = 0;           // 不持有
  let hold = -prices[0];  // 持有

  for (let i = 1; i < prices.length; i++) {
    const newCash = Math.max(cash, hold + prices[i] - fee);
    const newHold = Math.max(hold, cash - prices[i]);
    cash = newCash;
    hold = newHold;
  }

  return cash;
}

变体2: 买卖股票（含两次手续费）

// 卖出时扣一次，卖出后再买扣一次
function maxProfitWithTwoFees(prices: number[], fee1: number, fee2: number): number {
  let cash = 0;
  let hold = -prices[0];
  let inTransaction = false; // 是否在交易中

  for (const price of prices) {
    if (!inTransaction) {
      // 不持有，可以买
      hold = Math.max(hold, cash - price - fee2);
    } else {
      // 持有，可以卖
      cash = Math.max(cash, hold + price - fee1);
    }
  }

  return cash;
}

变体3: 持有任意数量股票

// 问题: 最多能同时持有 maxHold 股
function maxProfitWithKStocks(k: number, prices: number[]): number {
  const n = prices.length;
  if (k >= n / 2) {
    // 等价于无限交易
    let profit = 0;
    for (let i = 1; i < n; i++) {
      profit += Math.max(0, prices[i] - prices[i - 1]);
    }
    return profit;
  }

  const dp = Array.from({ length: k + 1 }, () => [0, -prices[0]]);

  for (let i = 1; i < n; i++) {
    for (let j = 1; j <= k; j++) {
      dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
      dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - prices[i]);
    }
  }

  return dp[k][0];
}

---

9. 股票问题解题套路

四步法

1. 确定状态数
   - 普通交易: 2个状态 (持有/不持有)
   - 含冷冻期: 3个状态 (持有/不持有/冷冻)
   - k次交易: 2k个状态

2. 初始化
   - buy[i] = -prices[0] (假设第0天买入)
   - sell[i] = 0

3. 状态转移
   - 买入: buy[i] = max(buy[i], sell[i-1] - price)
   - 卖出: sell[i] = max(sell[i], buy[i] + price - fee)

4. 结果
   - 必须卖出: sell[k]
   - 可买可不买: max(sell)

快速判断题类型

看到"最多k次交易" → 用 k 次交易模板
看到"冷冻期" → 加冷冻状态
看到"手续费" → 卖出时扣 fee
看到"k >= n/2" → 变成无限交易

看到"只能交易一次" → 直接 max - min
看到"每天都要买或卖" → 贪心即可

---

参见: **DP算法索引**