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

发表于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，714. Best Time to Buy and Sell Stock with Transaction Fee

先看题目描述

rt2a7j.png

大意就是给定一个数组，代表股票每天的价格，手上只能持有一只股票，我们可以以低价买入然后高价卖出然后来获取收益，但是当卖出股票时会收取金额为 fee 的手续费，让我们返回最后的最大收益

算法和思路

动态规划

这是很容易想到的方法，我们用 dp[i][0] 代表第 i 天手上持有股票时可获取的最大收益，用 dp[i][1] 代表手上不持有股票时可获取的最大收益，则状态转移方程如下：

  • dp[i][0] = max{dp[i - 1][0]，dp[i - 1[1] - prices[i]}
  • dp[i][1] = max{dp[i - 1][1]，dp[i - 1][0] + prices[i] - fee}

初始时 dp[0][0] = -prices[0]，dp[0][1] = 0，最后返回 dp[n - 1][1] 即可，因为 dp[n - 1][1] 一定大于 dp[n - 1][0]

贪心

虽然知道这题肯定有贪心的做法，但怎么也想不出来该怎么用贪心算法解决，最后看了题解才知道该怎么做

方法一中，我们将手续费放在卖出时进行计算。如果我们换一个角度考虑，将手续费放在买入时进行计算，那么就可以得到一种基于贪心的方法

我们用 buy 表示在最大化收益的前提下，如果我们手上拥有一支股票，那么它的最低买入价格是多少。在初始时，buy 的值为 prices[0] 加上手续费 fee。那么当我们遍历到第 i (i>0) 天时：

  • 如果当前的股票价格 prices[i] + fee < buy，那么与其使用 buy 的价格购买股票，不如使用 prices[i] + fee 的价格购买股票，更新 buy 为 prices[i] + fee
  • 如果当前的股票价格 prices[i] > buy，那么我们可以直接卖出股票并获得 prices[i] - buy 的收益。但实际上，此时卖出股票可能并不是全局最优的(例如第二天股票继续上升)，因此我们可以提供一个反悔操作，看作当前手上拥有一支买入价格为 prices[i] 的股票，将 buy 更新为 prices[i]。这样一来，如果下一天股票继续上升，我们会获得 prices[i + 1] - prices[i] 的收益，加上这一天 prices[i] - buy 的收益，恰好就等于在这一天不进行任何操作，而在下一天卖出股票的收益
  • 对于其余的情况，prices[i] 落在区间 [buy - fee，buy] 内，它的价格没有低到我们放弃手上的股票去选择它，也没有高到我们可以卖出股票获得收益，因此我们不进行任何操作

上面的贪心思想可以浓缩成一句话，即当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。在遍历完数组 prices 后，我们就得到了最大的总收益

算法源码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; 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);
        }
        return dp[len - 1][1];
    }
}

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int buy = Integer.MAX_VALUE;
        int profit = 0;
        for (int price : prices) {
            if (price + fee < buy) {
                buy = price + fee;
            } else if (buy < price){
                profit += price - buy;
                buy = price;
            }
        }
        return profit;
    }
}