# 买卖股票的最佳时机含手续费
给定一个整数数组`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.
```

## 题解

```javascript
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    const n = prices.length;
    const dp = new Array(2).fill(0).map(v => new Array(n).fill(0));
    dp[0][0] = -prices[0];
    dp[1][0] = 0;
    for (let i = 1; i < n; ++i) {
        // 该点最终状态为持有：继续持有/未持有买入
        dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1] - prices[i]);
        // 该点最终状态为持有未持有：继续未持有/持有卖出
        dp[1][i] = Math.max(dp[1][i - 1], dp[0][i - 1] + prices[i] - fee);
    }
    return dp[1][n - 1];
};
```

## 思路
动态规划的方式，根据题目示例，可以打印一个表格。

| 状态 | 1 | 3 | 2 | 8 | 4 | 9 | 
| --- | --- | --- | --- | --- | --- | --- | 
| 持有 | -1 | -1 | -1 | -1 | 1 | 1 |
| 未持有 | 0 | 0 | 0 | 5 | 5 | 8 |

需要解释一下这个表格，考虑到不能同时参与多笔交易，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态，我们给予其两个状态，第一个持有状态为持有，即第`i`天交易完后手里持有一支股票的最大利润，第二个为未持有状态，即第`i`天交易完后手里没有股票的最大利润，考虑`dp[0][i]`按状态转移，那么可能的转移状态为前一天已经持有一支股票，即`dp[1][i−1]`，或者前一天结束时还没有股票即`dp[1][i−1]`，这时候我们要将其买入，并减`prices[i]`的收益，可以列出如下的转移方程`dp[1][i]=max{dp[1][i−1],dp[0][i−1]−prices[i]}`；同样再考虑考虑`dp[1][i]`的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即`dp[1][i−1]`，或者前一天结束的时候手里持有一支股票，即`dp[0][i−1]`，这时候我们要将其卖出，并获得`prices[i]`的收益，但需要支付`fee`的手续费,因此为了收益最大化，我们列出如下的转移方程`dp[0][i]=max{dp[0][i−1],dp[1][i−1]+prices[i]−fee}`，对于所有的初始化状态，根据状态定义我们可以知道第`0`天交易结束的时候有`dp[0][0]=0`以及`dp[1][0]=−prices[0]`，之后只要从前往后依次计算状态即可。首先定义`n`为数组长度，直接使用构造函数生成一个`2 * n`的数组并将其填充为`0`，外层数组填充`0`的原因是`map`会跳过`empty`数组空位，实际上在外层数组填充任何值都可以，会使用`map`回调函数的返回值覆盖，之后定义初始化的第一列的值，之后定义循环，构建列表，具体的规则可以参考上述的表格解释，之后返回第二行的最后一个值即可。



## 每日一题

```
https://github.com/WindrunnerMax/EveryDay
```

## 参考

```
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
```