Best Time to Buy and Sell Stock With Transaction Fee

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

分析

状态定义
- 定义 f[i][0] ：表示第 i 天结束时，手中没有持有股票的最大利润
- 定义 f[i][1] ：表示第 i 天结束时，手中持有股票的最大利润
状态转移
- 在第 i 天，可以有以下两种状态转移：
- 手中没有股票：
  - 可能来自前一天也没有股票，即 f[i-1][0]
  - 或者今天卖出股票，产生利润 f[i-1][1] + prices[i-1] - fee（卖出价格减去手续费）。
  - 转移公式：f[i][0] = max(f[i-1][0], f[i-1][1] + prices[i-1] - fee)
- 手中持有股票：
  - 可能来自前一天也持有股票，即 f[i-1][1]
  - 或者今天买入股票，产生利润 f[i-1][0] - prices[i-1]
  - 转移公式：f[i][1] = max(f[i-1][1], f[i-1][0] - prices[i-1])
初始状态
- 第 0 天没有股票：f[0][0] = 0（没有任何利润）
结果
- 最后一天手中没有股票的最大利润 f[n][0]

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    int maxProfit(vector<int>& prices, int fee)
    {
        int n = prices.size(), INF = 0x3f3f3f3f;
        // 动态规划数组，初始化为负无穷（表示无效状态）
        std::vector<std::vector<int>> f(n + 1, std::vector<int>(2, -INF));
        f[0][0] = 0; // 第 0 天未持有股票的利润为 0
        int res = 0; // 最大利润

        for (int i = 1; i <= n; ++i)
        {
            // 第 i 天未持有股票的最大利润
            f[i][0] = std::max(f[i - 1][0], f[i - 1][1] + prices[i - 1] - fee);
            // 第 i 天持有股票的最大利润
            f[i][1] = std::max(f[i - 1][1], f[i - 1][0] - prices[i - 1]);
            // 更新最大利润
            res = std::max(res, f[i][0]);
        }
        return res;
    }
};