122. 买卖股票的最佳时机 II

发表于 分类于 阅读次数： Waline： 本文字数： 952 阅读时长 ≈ 3 分钟

考点

  • 状态机DP

思路

1. 状态设计

令共有 \(n\) 天，价格数组为 prices[0..n-1]。 代码中用的是「1-based 的天数下标」：i 表示「前 \(i\) 天处理完后」的状态。

定义二维 DP：

  • \(f[i][0]\)：处理完前 \(i\) 天后，手上不持股 时的最大利润
  • \(f[i][1]\)：处理完前 \(i\) 天后，手上持有一股 时的最大利润

其中 i 的范围是：

  • 代码中：\(i = 0, 1, 2, \dots, n\)
  • 第 \(i\) 天对应的价格在 prices[i-1]，所以转移中使用 prices[i-1]。

直观理解：

  • \(i\) 是「天数前缀长度」
  • 0 / 1 是「当前是否持股」这个二元状态。

2. 初始化设计

2.1 第 0 天的含义

\(i = 0\) 表示「还没有开始任何交易」的时刻，也就是第 0 天结束，实际上还没进入第 1 天：

  • 没有做过任何买卖
  • 手上自然是不持股

对应初始化为： \[ f[0][0] = 0 \] 表示： 还没开始，手上没股票，利润为 0。

2.2 不可能状态的初始化

\[ f[0][1] = \text{neg} \]

其中 neg = 0xcfcfcfcf 是一个非常大的负数，可以视作 \(-\infty\)。

含义： 在「第 0 天结束」这个时刻，不可能已经持有股票，因为我们还没开始任何操作。 所以这一状态被设为负无穷，表示不合法/极差的状态，保证之后所有转移都不会从这里「占便宜」。

这也是一个常见的 DP 策略： 对「不可能达到的状态」初始化为 \(-\infty\)，从而让 max 比较时自然忽略掉它。

3. 状态转移推导

在第 \(i\) 天（使用的价格是 prices[i-1]），我们从第 \(i-1\) 天的两种状态进行转移。

3.1 不持股状态 \(f[i][0]\)

第 \(i\) 天结束时，不持股，可能来自两种情况：

  1. 昨天也不持股，今天什么都不干： \[ f[i-1][0] \;\to\; f[i][0] \]

  2. 昨天持股，今天把股票卖掉：

    • 昨天结束时利润为 \(f[i-1][1]\)
    • 今天以价格 prices[i-1] 卖出一股，利润增加 prices[i-1]

    \[ f[i-1][1] + \text{prices}[i-1] \;\to\; f[i][0] \]

所以取最大值： \[ f[i][0] = \max\Big( f[i-1][0],\ f[i-1][1] + \text{prices}[i-1] \Big) \] 代码对应：

1
f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i - 1]);

3.2 持股状态 \(f[i][1]\)

第 \(i\) 天结束时，持股，也有两种情况：

  1. 昨天就已经持股，今天不操作，继续拿着： \[ f[i-1][1] \;\to\; f[i][1] \]

  2. 昨天不持股，今天买入一股：

    • 昨天的利润为 \(f[i-1][0]\)
    • 今天以价格 prices[i-1] 买入一股，利润减少 prices[i-1]

    \[ f[i-1][0] - \text{prices}[i-1] \;\to\; f[i][1] \]

所以取最大： \[ f[i][1] = \max\Big( f[i-1][1],\ f[i-1][0] - \text{prices}[i-1] \Big) \] 代码对应：

1
f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i - 1]);

4. 答案设计

处理完所有 \(n\) 天后，最终的答案是： \[ \text{ans} = f[n][0] \] 原因：

  • 手上不持股时，利润才是「真正已经实现」的
  • 若还持股（状态 \(f[n][1]\)），说明还有一股没卖，相当于少赚了一次卖出的价差

对应代码：

1
return f[n][0];

5. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    const int maxn = 3e4 + 5, neg = 0xcfcfcfcf;
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int f[maxn][2];
        f[0][0] = 0, f[0][1] = neg;
        for (int i = 1; i <= n; ++i) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i - 1]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i - 1]);
        }
        return f[n][0];
    }
};

由于实际上只用了两个变量，滚动数组优化空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    const int maxn = 3e4 + 5, neg = 0xcfcfcfcf;
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int x = 0, y = neg;
        for (int i = 1; i <= n; ++i) {
            int p, q;
            p = max(x, y + prices[i - 1]);
            q = max(y, x - prices[i - 1]);
            x = p, y = q;
        }
        return x;
    }
};