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

题目描述

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。 返回获得利润的最大值。 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。 示例 1： 输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8 示例 2： 输入：prices = [1,3,7,5,10,3], fee = 3 输出：6

提示： 1 <= prices.length <= 5 * 10(4) 1 <= prices[i] < 5 * 10(4) 0 <= fee < 5 * 10(4)

题目解析

题目在说什么

这道题是让你买卖股票，但每次买卖都要付一笔固定的手续费。你可以买卖很多次，但手里最多只能持有一股股票（就是不能同时买两只）。目标是算出最多能赚多少钱。

举个例子：股票价格是 [1, 3, 2, 8, 4, 9]，手续费是 2 元。 一种赚法：第 0 天 1 元买，第 3 天 8 元卖，赚 (8-1)-2 = 5 元；然后第 4 天 4 元买，第 5 天 9 元卖，赚 (9-4)-2 = 3 元，总共 8 元。 另一种赚法：如果只买卖一次，比如 1 元买 9 元卖，赚 (9-1)-2 = 6 元，比 8 元少。所以关键是要决定什么时候买卖，才能扣掉手续费后总利润最大。

思路是怎么来的

想象你是一个小贩，每天去市场看苹果的价格。你可以今天买进，过几天卖出，但每次交易（买+卖）要交 2 元摊位费。你手里最多只能拿一箱苹果（不能同时囤两箱）。

关键问题：每天结束时，你只有两种状态——要么手里有苹果（持有股票），要么手里没苹果（不持有股票）。我们只需要记录这两种状态下，你口袋里最多有多少钱（利润）。

为什么这样想？因为明天的决策只取决于今天的状态。比如：

• 如果你今天手里有苹果，明天你可以选择继续拿着，或者卖掉。
• 如果你今天手里没苹果，明天你可以选择继续空仓，或者买进。

手续费怎么处理？我们可以把手续费看作买苹果时额外多付的钱。比如苹果标价 5 元，手续费 2 元，那买进的实际成本就是 7 元。卖出时就不用再付手续费了。

这样，问题就变成了：每天根据昨天的状态，计算今天两种状态下的最大利润。这就是动态规划——把大问题拆成一天一天的小问题，每个小问题只跟昨天有关。

代码逐步拆解

我们来看参考代码是怎么一步步实现的。为了更清楚，我会把代码拆成几块解释。

1. 准备工作

int length = prices.length;
int[][] dp = new int[length][2];

• length 是总天数。
• dp 是一个表格，有 length 行（每天一行），每行有 2 列：
• dp[i][0]：第 i 天结束时，不持有股票的最大利润。
• dp[i][1]：第 i 天结束时，持有股票的最大利润。

2. 初始化第一天（第 0 天）

dp[0][0] = 0;
dp[0][1] = - (prices[0] + fee);

• 第 0 天不持有股票：你什么都没做，利润是 0。
• 第 0 天持有股票：你只能是在第 0 天买入了。买入花了 prices[0] 元，还要付 fee 元手续费，所以你的利润是 -(prices[0] + fee)（负数，表示你花了钱）。

3. 从第 1 天开始，每天计算两种状态

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

先看 `dp[i][0]`（今天不持有股票）： 有两种可能让你今天不持有股票： 1. 昨天就不持有，今天啥也没做 → 利润就是昨天的 dp[i-1][0]。 2. 昨天持有股票，今天把它卖了 → 利润 = 昨天持有时的利润 dp[i-1][1] + 今天卖出的收入 prices[i]（注意：卖出不用再付手续费，因为手续费已经在买入时付过了）。

取这两种可能中利润更大的那个。