Java 求解买卖股票的最佳时机含手续费
文章目录
一、题目
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
二、题解
本题有手续费，所以需要考虑获得利润，需要考虑买卖利润不足以手续费的情况
如果使用贪心策略，就是最低值买，最高值（算上手续费还盈利）就卖
也就是需要找到：买入日期，卖出日期
买入日期：也就是最低点
卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。
所以：
- 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
- 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
- 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
三、代码
class Solution {
public int maxProfit(int[] prices, int fee) {
// 记录最小的价格
int minPrice = prices[0];
// 记录最终的收益
int res = 0;
for (int price : prices) {
// 更新最小的价格
if (price < minPrice) {
minPrice = price;
}
// minPrice = Math.min(minPrice,price);
// 如果当前价格大于最小的买入点+手续费，则表示可以卖出
// 但是此时的价格不一定是最后的卖出价格
if (price > minPrice + fee) {
// 此时不一定是最后卖出的价格
res += price - minPrice - fee;
// 这里是为了只收一次手续费
// 只有下次的价格大于当前价格时，才会继续卖，同时只收取一次卖出费用
// 比如1买入，4卖出，后面又出来5,5大于4-1，所以5才是真正卖出的位置
// 比如第一次1买入，4卖出，假定手续费2，收益为1，4不一定是最后卖出的价格，如果后面遇到了5，5相比4收益多了1
minPrice = price - fee;
}
}
return res;
}
}
四、总结
题目也用到了贪心的思路，区别当前卖出和最后卖出的处理
五、动态规划解法
分析题意，一共两种解法，要么今天买入或者保持买入的状态，要么今天卖出或者保持卖出的状态
（1）确定 dp 数组及其下标含义：表示当前金额的最大数值
（2）确定递推表达式
（3）确定初始化
（4）确定递归逻辑
class Solution {
public int maxProfit(int[] prices, int fee) {
// dp[i][0] 表示第i天买入股票或者保持买入状态的最大金额
// dp[i][1] 表示第i天卖出股票或者保持卖出状态的最大金额
int[][] dp = new int[prices.length][2];
// 第一天买入股票的最大金额
dp[0][0] = 0 - prices[0];
// 第一天卖出股票的最大金额
dp[0][1] = 0;
for (int i = 1; i < prices.length; i++) {
// 持有买入分两种：要么保持买入的状态，要么新买入，取最大值
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - fee - prices[i]);
// 要么保持卖出状态，要么新卖出，取最大值
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - fee + prices[i]);
}
return dp[prices.length][1];
}
}