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];
    }
}