本文主要是介绍「动态规划」买卖股票的最佳时机，如何处理手续费？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个整数数组prices，其中prices[i]表示第i天的股票价格；整数fee代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要支付一次手续费。
- 输入：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。
- 输入：prices = [1,3,7,5,10,3]，fee = 3，输出：6。
提示：1 <= prices.length <= 5 * 10^4，1 <= prices[i] < 5 * 10^4，0 <= fee < 5 * 10^4。
我们用动态规划的思想来解决这个问题。
确定状态表示：根据经验和题目要求，我们用dp[i]表示：在第i天结束时，此时的最大利润。
在第i天结束时，如果手中有股票，我们就处于买入状态；如果手中没有股票，我们就处于卖出状态。所以状态表示可以细分为：
- 用f[i]表示：在第i天结束时，处于买入状态，此时的最大利润。
- 用g[i]表示：在第i天结束时，处于卖出状态，此时的最大利润。
推导状态转移方程：问题的关键在于如何计算利润。如果我们买入股票，那么利润就要减去股票当天的价格；如果我们卖出股票，那么利润就要加上股票当天的价格。除此之外，还要考虑手续费，根据题目要求，这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要支付一次手续费，我们选择在卖出股票时支付一次手续费，所以在卖出股票时利润要减去手续费。
我们考虑最近的一步，即第i - 1天的状态：
- 考虑f[i]，在第i天结束时处于买入状态，此时的最大利润是以下情况的最大值。
- 如果在第i - 1天结束时处于买入状态，那么在第i天什么都不做，此时的最大利润就是在第i - 1天结束时处于买入状态的最大利润，即f[i - 1]。
- 如果在第i - 1天结束时处于卖出状态，那么就要在第i天买入股票，此时的最大利润是在第i - 1天结束时处于卖出状态的最大利润减去股票在第i天的价格，即g[i - 1] - prices[i]。
- 考虑g[i]，在第i天结束时处于卖出状态，此时的最大利润是以下情况的最大值。
- 如果在第i - 1天结束时处于买入状态，那么就要在第i天卖出股票，此时的最大利润是在第i - 1天结束时处于买入状态的最大利润加上股票在第i天的价格，再减去手续费，即f[i - 1] + prices[i] - fee。
- 如果在第i - 1天结束时处于卖出状态，那么在第i天什么都不做，此时的最大利润就是在第i - 1天结束时处于卖出状态的最大利润，即g[i - 1]。
综上所述：f[i] = max(f[i - 1], g[i - 1] - prices[i])，g[i] = max(f[i - 1] + prices[i] - fee, g[i - 1])。
初始化：根据状态转移方程，我们要初始化f[0]和g[0]的值，防止越界。
- f[0]表示：在第0天结束时处于买入状态下的最大利润。一开始利润是0，在第0天买入股票，第0天结束时的最大利润就是-prices[0]。
- g[0]表示：在第0天结束时处于卖出状态下的最大利润。一开始利润是0，在第0天什么都不做，利润仍然是0。
综上所述：f[0] = -prices[0]，g[0] = 0。
填表顺序：根据状态转移方程，f[i]和g[i]都依赖于f[i - 1]和g[i - 1]，所以要沿着i增大的方向同时填f表和g表。
返回值：假设总共有n天，那么第i天，i的范围就是[0, n - 1]。要想获得最大利润，在第n - 1天结束时必须处于卖出状态，否则在第n - 1天卖出股票就能获得更多的利润。根据状态表示，我们最终要返回第n - 1天结束时处于卖出状态的最大利润，即g[n - 1]。
细节问题：由于f表和g表的下标范围都是[0, n - 1]，所以规模都是1 x n。
时间复杂度：O(N)，空间复杂度：O(N)。
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();// 创建dp表vector<int> f(n);auto g = f;// 初始化f[0] = -prices[0];// 填表for (int i = 1; i < n; i++) {f[i] = max(f[i - 1], g[i - 1] - prices[i]);g[i] = max(f[i - 1] + prices[i] - fee, g[i - 1]);}// 返回结果return g[n - 1];}
};这篇关于「动态规划」买卖股票的最佳时机，如何处理手续费？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
