714. 买卖股票的最佳时机含手续费
目录
一.题目描述
二.解题思路
三.代码
四.重点：要是总结一下动态规划的最厉害的一点，会用哪个词语？
一.题目描述
给定一个整数数组
prices，其中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 * 1041 <= prices[i] < 5 * 1040 <= fee < 5 * 104
二.解题思路
先声明一点：要采用【动态规划】。
核心思路：
1. 用状态来思考
每天收盘时，你只有两种状态：
状态A（空仓）：手里没股票，兜里有多少钱
状态B（持仓）：手里有1股股票，兜里有多少钱（已经扣除了买股票的成本）
2.状态怎么转移
从第i天到第i+1天：
空仓状态怎么来？
- 昨天就空仓，今天啥也没干 → 钱不变
- 昨天持仓，今天把股票卖了 → 昨天的钱 + 今天卖出价 - 手续费
持仓状态怎么来？
- 昨天就持仓，今天啥也没干 → 钱不变
- 昨天空仓，今天买入股票 → 昨天的钱 - 今天买入价
3. 核心公式
新空仓 = max(旧空仓, 旧持仓 + 今天价格 - 手续费) 新持仓 = max(旧持仓, 旧空仓 - 今天价格)思考：为什么这叫动态规划而不是暴力搜索？
对比项 暴力搜索 动态规划 怎么做 枚举所有买卖组合 只记录两种状态的最优值 状态数 指数级（3^n） 常数级（2个） 时间复杂度 O(3^n) 不可行 O(n) 可行 空间复杂度 巨大 O(1) 动态规划的精髓：用状态代表一类情况，舍去具体路径，只保留最优值。
三.代码
class Solution { public int maxProfit(int[] prices, int fee) { // 边界条件判断 if (prices == null || prices.length == 0) { return 0; } // 初始化第0天的状态 int cash = 0; // 不持有股票时的最大利润 int hold = -prices[0]; // 持有股票时的最大利润（负值表示买入花了钱） // 从第1天开始遍历 for (int i = 1; i < prices.length; i++) { // 保存旧值（Java中必须显式保存，因为赋值是顺序执行的） int prevCash = cash; int prevHold = hold; // 更新两个状态 // 今天不持股 = max(昨天就不持股, 昨天持股 + 今天卖出 - 手续费) cash = Math.max(prevCash, prevHold + prices[i] - fee); // 今天持股 = max(昨天就持股, 昨天不持股 - 今天买入) hold = Math.max(prevHold, prevCash - prices[i]); } // 最后一天不持股的利润一定最大 return cash; } }运行结果
四.重点：要是总结一下动态规划的最厉害的一点，会用哪个词语？
"状态压缩"或者"降维打击"。
为什么是这个词？
动态规划最厉害的地方，就是把「所有可能的路径」压缩成「几个关键状态」。
对比一下：
暴力搜索：记录每条具体路径
路径1：第1天买，第3天卖，第5天买...
路径2：第1天买，第4天卖，第6天买...
路径3：第2天买，第5天卖...
... 指数级增长
动态规划：只记录两个状态
状态A：所有以「空仓」结尾的路径中，利润最大的那个值
状态B：所有以「持仓」结尾的路径中，利润最大的那个值
打个比方
这就像：
暴力搜索：你要找出去北京的最短路线，就把全国所有可能的路线都走一遍
动态规划：你只记录"到每个城市的最短距离"，不管你是怎么来的
带来的效果
维度 暴力搜索 动态规划 状态数量 指数级 常数级 时间复杂度 O(3ⁿ) 不可算 O(n) 轻松算 n=50时 3⁵⁰ ≈ 7×10²³ 种可能 50次计算 这就是为什么叫降维打击——把指数级的问题，降成了线性级。
以上就是本篇文章的全部内容，喜欢的话可以留个免费的关注呦~~~