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

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

考点

  • 状态机DP

思路

一、状态定义

设第 \(i\) 天结束后的状态为： \[ f[i][0] = \text{第 } i \text{ 天结束时，不持有股票的最大利润} \] 每天只有两种互斥状态：

  • 空仓
  • 持有一股

手续费统一在卖出时结算。

二、初始值设计（最关键）

在 第 0 天（尚未开始交易）： \[ f[0][0] = 0 \] 含义： 尚未发生任何操作，不持股时的利润为 0。

\[ f[0][1] = -\infty \]

含义： 在第 0 天不可能已经持有股票，这是一个非法状态，必须用负无穷屏蔽（代码中用 0xcfcfcfcf 实现）。

三、状态转移方程

设当天价格为 \(prices[i-1]\)。

1. 持股状态转移

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

含义：

  • 昨天已经持股，今天继续持有
  • 昨天空仓，今天买入一股

手续费 不在买入时扣除。

2. 空仓状态转移（卖出并扣手续费）

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

含义：

  • 昨天空仓，今天继续空仓
  • 昨天持股，今天卖出，并 扣除手续费

四、最终结果

\[ \boxed{f[n][0]} \]

原因： 题目要求最终 未持股状态 下的最大利润。 若最终仍持股，则最后一笔交易未完成，不满足题意。

五、代码

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

滚动数组：

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