515，动态规划解买卖股票的最佳时机含手续费

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

Since you are like no other being ever created since the beginning of time, you are incomparable.

因为你和有史以来任何人类都不相同，所以你是无可比拟的。

问题描述

给定一个整数数组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.

注意:

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

动态规划解决

这题和492，动态规划和贪心算法解买卖股票的最佳时机 II非常类似，不同的是第492题不需要手续费，而这个题需要手续费。参照第492题我们来看下这题使用动态规划该怎么解决。

定义

dp[i][0]表示第i天交易完之后手里没有股票的最大利润。

dp[i][1]表示第i天交易完之后手里持有股票的最大利润。

当天交易完之后手里没有股票可能有两种情况:

一种是当天没有进行任何交易，又因为当天手里没有股票，所以当天没有股票的利润只能取前一天手里没有股票的利润。
一种是把当天手里的股票给卖了，既然能卖，说明手里是有股票的，所以这个时候当天没有股票的利润要取前一天手里有股票的利润加上当天股票能卖的价格再减去手续费。

这两种情况我们取利润最大的即可，所以可以得到

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

当天交易完之后手里持有股票也有两种情况：

一种是当天没有任何交易，又因为当天手里持有股票，所以当天手里持有的股票其实前一天就已经持有了。
还一种是当天买入了股票，当天能卖股票，说明前一天手里肯定是没有股票的。

我们取这两者的最大值，所以可以得到

dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);

动态规划的递推公式有了，那么初始条件是什么呢，就是第0天

如果买入：dp[0][1]=-prices[0];

如果没买：dp[0][0]=0;

有了递推公式和边界条件，代码很容易就写出来了。

 1public int maxProfit(int[] prices, int fee) {
 2    //边界条件判断
 3    if (prices == null || prices.length < 2)
 4        return 0;
 5    int length = prices.length;
 6    int[][] dp = new int[length][2];
 7    //初始条件
 8    dp[0][1] = -prices[0];
 9    dp[0][0] = 0;
10    for (int i = 1; i < length; i++) {
11        //递推公式
12        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
13        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
14    }
15    //最后一天肯定是手里没有股票的时候，利润才会最大，
16    //只需要返回dp[length - 1][0]即可
17    return dp[length - 1][0];
18}

代码优化

上面计算的时候我们看到当天的利润只和前一天的记录有关，没必要使用一个二维数组，只需要使用两个变量：

一个记录当天交易完之后手里持有股票的最大利润。

一个记录当天交易完之后手里没有股票的最大利润。

来看下代码

 1public int maxProfit(int[] prices, int fee) {
 2    //边界条件判断
 3    if (prices == null || prices.length < 2)
 4        return 0;
 5    int length = prices.length;
 6    //初始条件
 7    int hold = -prices[0];//持有股票
 8    int noHold = 0;//没持有股票
 9    for (int i = 1; i < length; i++) {
10        //递推公式转化的
11        noHold = Math.max(noHold, hold + prices[i] - fee);
12        hold = Math.max(hold, noHold - prices[i]);
13    }
14    //最后一天肯定是手里没有股票的时候利润才会最大，
15    //所以这里返回的是noHold
16    return noHold;
17}