力扣714-买卖股票的最佳时机含手续费

一、原题题目

1.1 题目

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

1.2 示例

示例一

输入： 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.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

二、解题思路（动态规划）

2.1 题目理解

题前感慨（时间紧不用看，跳至【言归正传】部分）

给定每日股票价格的数组，每天可以选择是否买入/卖出，持有时不能再次买入，每笔交易有固定的手续费，求可获得的最大利润。给定每日股票价格的数组，每天可以选择是否买入/卖出，持有时不能再次买入，每笔交易有固定的手续费，求可获得的最大利润。

这是一道入门的动态规划题目……当说出这句话的时候表示说话者已经对动态规划有所掌握了，所以能很快的分析出它是一道动态规划题，并且很容易就能想到什么状态变量，转移方程的所以它是一道简单的动态规划题目。但对于很多算法新手来说，难的是识别它是个动态规划题。

本文主要解决该算法题，下面会结合本题简单说到动态规划，动态规划的详细讲解自己也会全面的整理一份资料供自己总结复习，同时也分享出来给需要的网友参考~。

言归正传

【1.识别动态规划】动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态，此问题当中我们的初试状态就是第0天开始，结束状态就是第n天结束。中间的买入/卖出就是中间决策的选择。

【2.确定状态定义状态变量】知道是动态规划题后就老老实实的确定状态和定义状态变量，如何正确合理的确定状态也至关重要，例如这里可以以每天交易结束后手里是否有股票为状态，两种状态：有股票，没有股票。我们的目的是求最后的最大利润的，所以定义状态变量可以这样定义：dp[i][0] 表示第 i 天交易结束后手里没有股票的最大利润。dp[i][1] 表示第 i 天交易结束后手里有股票的最大利润。

【3.推导状态转移方程】先考虑 dp[i][0] 的转移方程，第 i 天结束，手里没有股票，那么一定是今天没有买入。可能的状态有前一天可能是也没有股票状态 dp[i-1][0]，或前一天结束时手里有股票 dp[i-1][1]被我今天卖了。因此转移方程为：
$$
dp[i][0] = max{dp[i-1][0],dp[i-1][1]+prices[i]-fee}
$$
在考虑 dp[i][1] 的转移方程，第 i 天结束后，手里有股票，那么一定是今天没有卖出。可能的状态有前一天本来就是有股票状态 dp[i-1][1]，或者前一天结束时没有股票dp[i-1][0]，但我今天买入了。因此转移方程为：
$$
dp[i][1] = max{dp[i-1][1],dp[i-1][0]-prices[i]}
$$
【4.确定边界】其实就是确定初始状态，第0天交易结束时有 dp[0][0] = 0，dp[0][1] = -prices[0]。

2.2 详细代码（Java）

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices.length <= 1) return 0;
        int[][] dp = new int[prices.length][2];     // 状态变量，存储每天有或没有股票的最大收益
        dp[0][0] = 0;           // 初始值，第0天没股票即没有买入，收益为0
        dp[0][1] = -prices[0];  // 初始值，第0天有股票即买入了，收益为-prices[0]
        for (int i = 1;i<prices.length;i++){        // 循环更新每天的状态
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
        }
        return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]); // 返回最后一天两种状态的最大值
    }
}

2.3 算法执行结果

算法性能不是很好，其他很多题友可能想出了更好的方法。这里重点总结该题对动态规划的运用，空间复杂度上可以稍微提升一下，因为在上述算法中定义了一个二维数组去求每一天的状态，是没有必要的，因为最后的输出只需要最后一天的。我们可以定义两个变量来存储就好了。

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices.length <= 1) return 0;
        int nothave = 0;            // 初始值，第0天没股票即没有买入，收益为0
        int have = -prices[0];      // 初始值，第0天有股票即买入了，收益为-prices[0]
        for (int i = 1;i<prices.length;i++){    // 循环更新状态值
            int n = nothave,y = have;           // 下面的更新中都要用到之前的值，所以要临时存储一下
            nothave = Math.max(n,y + prices[i] - fee);
            have = Math.max(y,n - prices[i]);
        }
        return Math.max(nothave,have);          // 返回两种状态的最大值
    }
}