一.通解

参考：https://leetCode-cn.com/circle/article/qiAgHn/
参考：https://leetCode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems

二.描述

给一个价格数组prices[]，index=i表示第i天的股票价格为prices[i]，每天最多只能执行一个买或卖的操作，给定最多进行k手交易（一手交易包括一次买和一次卖），求能获得的最大收益，一个人最多同时只能持有一个股票

三.通用递推方程

T[i][k]表示第i天结束时，在第0~i天最多进行k手交易后可以得到的最大收益，与T[i][k]相关的子问题有T[i-1][k],T[i-1][k-1],T[i]][k-1]，如何得到递推方程/转移方程
因为一个人买入一个股票前，必须这个人当前持有的股票为0，卖出一个股票前必须当前持有的股票数量为1，所以可以根据第i天可以执行的操作：buy/sell/rest来讨论
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])
T[i][k][0] = max(T[i-1][k][0], T[i-k][k][1] + prices[i])
最后肯定是T[i][k][0]的收益最大,因为肯定是卖得越多收益越高
注意: T[i][0][0]和T[i][0][1]都应该是0，因为不允许进行一手交易

四.特殊case

4.1 k=1，只能进行一手交易, leetcode-121

T[i][1][1] = max(T[i-1][1][1], T[i-1][0][0] - prices[i]) = max(T[i-1][1][1], -prices[i])
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])

4.2 k=+Infinity(可以进行无数手交易),leetcode-122

则k和k-1是一样的
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i]) = max(T[i-1][k][1], T[i-1][k][0] - prices[i])
T[i][k][0] = max(T[i-1][k][0], T[i-k][k][1] + prices[i])

4.3 k=2，可以进行2手交易, leetcode-123

T[i][2][1] = max(T[i-1][2][1], T[i-1][1][0]-prices[i])
T[i][2][0] = max(T[i-1][2][0], T[i-1][2][1]+prices[i])
T[i][1][1] = max(T[i-1][1][1], T[i-1][0][0]-prices[i])=max(T[i-1][1][1], -prices[i])
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1]+prices[i])

4.4 k为给定值， leetcode-188

k可以为0、1、2等
优化: 注意到一个事实,就是一手交易至少需要两天(一天买, 一天卖), 所以当k>=n/2(n为prices数组长度)时, k等价于无穷大,
当k更新顺序就从k更大的向k更小的更新，一样的k时从0->1更新。

4.5 k=+Infinity且有1天冷却期, leetcode-309

冷却期：昨天卖了股票，今天不能买，必须明天才可以买
所以如果想要第i天买股票，则T[i-1][k][0]必须保证没有在第i-1天卖股票,既第i-1天休息,所以T[i-1][k][0] = T[i-2][k][0]
T[i][k][1] = max(T[i-1][k][1], T[i-2][k][0]- prices[i])
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])

4.6 k=+Infinity且交易费用, leetcode-714

每笔交易都需要手续费, 可以在买入或卖出时扣除手续费
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i] - fee)
T[i][k][0] = max(T[i-1][k][0], T[i-k][k][1] + prices[i])
因为一个股票的价格可能低于交易手续费fee,所以要取T[i][k][0]和T[i][k][1]的较大值

五.leetcode题解

5.1 leetcode-121，一手交易

题目：prices[i]股票数组，prices[i] 是一支给定股票第 i 天的价格，只能完成一手交易，求所能获取的最大利润。
方法1：DP，通解方程

  1.     // 可参与的股票交易数k=1
  2.     // T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1]+price[i])
  3.     // T[i][1][1] = max(T[i-1][1][1], T[i-1][0][0]-price[i]) = max(T[i-1][1][1], -price[i])
  4.     // 设T[i][1][0]为t0, T[i][1][1]为t1
  5.     public int maxProfit(int[] prices) {
  6.         if(prices==null || prices.length==0){
  7.             return 0;
  8.         }
  9.         // 第0天要结束时手里有0个股票则只能选择rest
  10.         // 第0天要结束时手里有1个股票则只能选择买当天股票
  11.         int t0 = 0, t1 = -prices[0];
  12.         for(int i=1;i<prices.length;i++){
  13.             t0 = Math.max(t0, t1+prices[i]);
  14.             t1 = Math.max(t1, -prices[i]);
  15.         }
  16.         return t0;
  17.     }

方法2：贪心，得到prices[i]之前的历史最低价格minPrice，并认为买入价格就是历史最低价格，然后以prices[i]卖出即可，得到全局最大收益。

5.2 leetcode-122，无数手交易

题目：prices[i]股票数组，prices[i] 是一支给定股票第 i 天的价格，可以尽可能地完成更多的交易（多次买卖一支股票），求所能获取的最大利润。

  1.     // 可参与的股票交易数k=+Infinity
  2.     // T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1]+price[i])
  3.     // T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0]-price[i])
  4.     // 设T[i][k][0]为t0, T[i][k][1]为t1
  5.     public int maxProfit(int[] prices) {
  6.         // 第0天结束时, 手里要有0个股票则只能休息, 手里要有1个股票则只能买一个股票
  7.         int t0 = 0, t1 = -prices[0];
  8.         for(int i=1;i<prices.length;i++){
  9.             t0 = Math.max(t0, t1+prices[i]);
  10.             t1 = Math.max(t1, t0-prices[i]);
  11.         }
  12.         return t0;
  13.     }

5.3 leetcode-123，两手交易

题目：prices[i]股票数组，prices[i] 是一支给定股票第 i 天的价格，最多完成两手交易，求所能获取的最大利润。

  1.     // T[i][2][1] = max(T[i-1][2][1], T[i-1][1][0]-prices[i])
  2.     // T[i][2][0] = max(T[i-1][2][0], T[i-1][2][1]+prices[i])
  3.     // T[i][1][1] = max(T[i-1][1][1], T[i-1][0][0]-prices[i])=max(T[i-1][1][1], -prices[i])
  4.     // T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1]+prices[i])
  5.     // 设t10代表T[i][1][0] ,t11代表T[i][1][1], t20代表T[i][2][0], t21代表T[i][2][1; 更新顺序t20->t21->t10->t11, 因为公式里的依赖顺序
  6.     public int maxProfit(int[] prices) {
  7.         if(prices==null || prices.length==0){
  8.             return 0;
  9.         }
  10.         int t10 = 0, t11=-prices[0], t20 = 0, t21= -prices[0];
  11.         for(int i=1;i<prices.length;i++){
  12.             t20 = Math.max(t20, t21+prices[i]);
  13.             t21 = Math.max(t21, t10-prices[i]);
  14.             t10 = Math.max(t10, t11+prices[i]);
  15.             t11 = Math.max(t11, -prices[i]);
  16.         }
  17.         return t20;
  18.     }

5.4 leetcode-188，k手交易

题目：prices[i]股票数组，prices[i] 是一支给定股票第 i 天的价格，最多可以完成K手交易，求所能获取的最大利润。

  1.     //优化: 注意到一个事实,就是一手交易至少需要两天(一天买, 一天卖), 所以当k>=n/2(n为prices数组长度)时, k等价于无穷大,
  2.     // 当k<n/2时,就可以定义一个int[] v0,int[] v1,表示第i天结束的有0个stock、有1个stock的收益
  3.     // 更新顺序就从k更大的向k更小的更新，一样的k时从0->1更新。
  4.     public int maxProfit(int k, int[] prices) {
  5.         if(prices==null||prices.length==0){
  6.             return 0;
  7.         }
  8.         // k等价于无穷大
  9.         if(k>prices.length/2){
  10.             // T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1]+prices[i])
  11.             // T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0]-prices[i]) = max(T[i-1][k][1], T[i-1][k][0]-prices[i]);
  12.             int t0 = 0, t1 = -prices[0];
  13.             for(int i=1;i<prices.length;i++){
  14.                 t0 = Math.max(t0, t1+prices[i]);
  15.                 t1 = Math.max(t1, t0-prices[i]);
  16.             }
  17.             return t0;
  18.         }
  19.         // v0[j]表示允许最多j手事务第i天剩下0个stock的最大收益
  20.         int[] v0 = new int[k+1];
  21.         // v1[j]表示允许最多j手事务第i天剩下1个stock的最大收益
  22.         int[] v1 = new int[k+1];
  23.         // 初始化第0天允许i手事务剩下1个stock的收益
  24.         for(int i=1;i<=k;i++){
  25.             v1[i] = -prices[0];
  26.         }
  27.         // 更新顺序从k大的->k小的, 同一个k从0->1,可以写k=2的四个方程来总结规律
  28.         for(int i=1;i<prices.length;i++){
  29.             for(int j=k;j>=1;j--){
  30.                 v0[j] = Math.max(v0[j], v1[j]+prices[i]);
  31.                 v1[j] = Math.max(v1[j], v0[j-1]-prices[i]);
  32.             }
  33.         }
  34.         return v0[k];
  35.     }

5.5 leetcode-309，有一天冷静期

题目：prices[i]股票数组，prices[i] 是一支给定股票第 i 天的价格，可以尽可能地完成更多的交易（多次买卖一支股票），但有一天冷静期（比如第i-1天卖出的股票，第i天就不能买入股票），求所能获取的最大利润。

  1.     // T[i][k][1] = max(T[i-1][k][1], T[i-2][k][0]- prices[i])  
  2.     // T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
  3.     public int maxProfit(int[] prices) {
  4.         if(prices==null || prices.length==0){
  5.             return 0;
  6.         }
  7.         // 因为第i天的T[i][k][1]需要第i-2天的T[i-2][k][0], 所以
  8.         // 初始化第0天的T[0][k][0], T[0][k][1]
  9.         int t0 = 0, t1 = -prices[0];
  10.         // 初始化第-1天的T[-1][k][0]
  11.         int tBefore0 = 0;
  12.         for(int i=1;i<prices.length;i++){
  13.             int temp = t0;
  14.             // 更新T[i][k][0]
  15.             t0 = Math.max(t0, t1+prices[i]);
  16.             t1 = Math.max(t1, tBefore0-prices[i]);
  17.             tBefore0 = temp;
  18.         }
  19.         return t0;
  20.     }

5.5 leetcode-714，每手交易要手续费

题目：prices[i]股票数组，prices[i] 是一支给定股票第 i 天的价格，可以尽可能地完成更多的交易（多次买卖一支股票），但每手交易都需要手续费，求所能获取的最大利润。

  1.     // 设买入时扣除手续费
  2.     // T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i] - fee)
  3.     // T[i][k][0] = max(T[i-1][k][0], T[i-k][k][1] + prices[i])
  4.     public int maxProfit(int[] prices, int fee) {
  5.         if(prices==null || prices.length==0){
  6.             return 0;
  7.         }
  9.         int t0 = 0, t1 = -prices[0]-fee;
  10.         for(int i=1;i<prices.length;i++){
  11.             t0 = Math.max(t0, t1+prices[i]);
  12.             t1 = Math.max(t1, t0-prices[i]-fee);
  13.         }
  14.         // 因为一个股票的价格可能低于交易手续费fee,所以要取t0和t1的较大值
  15.         return Math.max(t0, t1);
  16.     }