DP5进阶

2020-05-22

对前四题进行一个总结

事实上这四种题型都是第4题的一个变体。
其中第一题为k=1时的情况
第二题为k=inf的情况
第三题为k=2的情况

接下来我们推出一个更加一般的形式，用一个三维dp数组来进行表示

1
2
3

dp[i][k][0] || dp[i][k][1] 
 //其中 0<=i<=n-1,  1<=k<=K  即i为在第几天进行交易，k为进行到了第几笔交易，而 第三个参数为 持有或者不持有
  //在这里我们定义 0为不持有， 1为持有  即我们最好的答案就是求dp[n-1][k][0]

在这里为什么是不持有股票利润最大我想应该很好理解，[0]表示股票已经卖出去了，即利润一定大于持有股票的情况

//今天我没有持有股票， 要么是我昨天也没有持有，即 dp[i-1][k][0] 或者是我们昨天持有然后今天卖出，即后者
dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
  //今天我持有股票，要么是我昨天就持有股票，要么是我昨天不持有股票，然后在今天买入
dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k][0]-prices[i])

有了上面的转移方程，我们再回过头来看看这四道题，按照惯例，我们还是从第一题开始

121、即此时就是k=1的情况

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int n=prices.length;
        int dp[][]=new int[n][2];
       
           for(int i=0;i<n;i++){
               if(i-1==-1){
                   dp[i][1]=-prices[i];
                   continue;
               }
              dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
               dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
           }
        return dp[n-1][0];
    }
}

很显然，如果每次我们都去处理这个边界情况，会很复杂，那么我们最好就用两个变量来代替这个dp数组，就像再最开始的那样，利用sell 和hold这个变量。

class Solution {
    public int maxProfit(int[] prices) {
        //在这里 hold表示持有股票的最大利润
        //sell表示不持有股票的最大利润
           if(prices.length==0) return 0;
        int hold=-prices[0];
        int sell=0;
        for(int i=1;i<prices.length;i++){
            hold=Math.max(hold,-prices[i]);
            sell=Math.max(sell,hold+prices[i]);
        }
        return Math.max(hold,sell);
    }
}

122、此时就是k=inf的情况

dp[i][k][0]=max{dp[i-1][k][0],dp[i-1][k][1]+prices[i]}
dp[i][k][1]=max{dp[i-1][k][1],dp[i-1][k][0]-prices[i]} 
//此时我们注意到k已经没有改变了
//我们可以直接用二维数组进行表示
dp[i][0]=max{dp[i-1][0],dp[i-1][1]+prices[i]}
dp[i][1]=max{dp[i-1][1],dp[i-1][0]-prices[i]}

这就是我们利用最普通的三维数组进行转换的结果，当然，这样的话我们还是要处理边界情况，非常麻烦，我们还是利用两个变量去存储这个二维数组，就像我们在最开始介绍的那样，再次不再赘述。

309、最佳买卖股票含冷冻期 k=inf+cool

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

此题的关键就是在卖出股票后，无法在第二天买入股票，并且此时这个k也是尽可能多，即k=inf

//我们仿造上面的状态转移方程，只需要在这里将dp数组稍微修改一下即可
dp[i][0]=max{dp[i-1][0],dp[i-1][1]+prices[i]}
//注意这里如果手里持有股票， 要么是前一天就持有股票，要么是前两天不持有股票，然后今天买入，因为有一天冷冻期
dp[i][1]=max{dp[i-1][1],dp[i-2][0]-prices[i]}

同样的，我们还是利用两个变量去存储这个状态

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
         int n=prices.length;
         int hold=-prices[0],sell=0;
        //用来代表冷冻期
        int pre=0;
        for(int i=0;i<prices.length;i++){
            int temp=sell;
            hold=Math.max(hold,pre-prices[i]);
             sell=Math.max(sell,hold+prices[i]);
            pre=temp;
        }
        return sell;
        
    }
}

714、 k=inf+free

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

//还是按照上面的思路，我们写出转移方程
dp[i][0]=max{dp[i-1][0],dp[i-1][1]+prices[i]}
dp[i][1]=max{dp[i-1][1],dp[i-1][0]-prices[i]-fee}
//这里的意思就是相当于我们在买入股票时需要减去一个手续费即可

转换成代码，可以看出来，与k=inf时没有什么区别

class Solution {
    public int maxProfit(int[] prices, int fee) {
          if(prices.length<2) return 0;
        int n=prices.length;
        int hold=-prices[0],sell=0;
        for(int i=1;i<n;i++){
            hold=Math.max(hold,sell-prices[i]);
            sell=Math.max(sell,hold+prices[i]-fee);
        }
        return sell;
    }
}

k=2 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

这个情况可能有点特殊，在之前要么k=1 要么k就是等于inf，基本都与k无关。那么在这里我们需要把k遍历一次

int[][][]dp=new int[n][2+1][2]
  for(int i=0;i<n;i++){
    for(int k=2;k>=1;k--){
      if(i-1==-1) {base case....}
      dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
        dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
    }
      return dp[n-1][2][0]
  }

或者我们可以吧所有的情况枚举一遍，就像我们在最开始那样

class Solution {
    public int maxProfit(int[] prices) {
          if(prices.length<2) return 0;
      //第一次持有或者不持有
        int fSell=0,fHold=-prices[0];
      //第二次持有或者不持有
         int sSell=0,sHold=-prices[0];
        for(int i=1;i<prices.length;i++){
            fSell=Math.max(fSell,fHold+prices[i]);
            fHold=Math.max(fHold,-prices[i]);
            sHold=Math.max(sHold,fSell-prices[i]);
            sSell=Math.max(sSell,sHold+prices[i]);
        }
        return sSell;
    }
}

188、k笔交易

if(prices.length<2) return 0;
       int n=prices.length;
       int [][][]dp=new int[n][max_k+1][2];
       for(int i=0;i<n;i++){
           for(int k=max_k;k>=1;k--){
                if(i-1==-1){
               dp[i][k][1]=-prices[0];
               continue;
           }
           dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
           dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
           }
          
       }
       return dp[n-1][max_k][0];

如果按照我们之前的想法，本题应该就是这样写，但是提交上去后会提示内存超了.原因是k已经破万，那么此时就有矛盾了，买入+卖出一共需要两天，即我们最多进行5000次交易。于是在k应该要<n/2 。这里我们做一个处理，复用在第二题中k=inf的情况

class Solution {
    public int maxProfit(int max_k, int[] prices) {
        if(prices.length<2) return 0;
        int n=prices.length;
        if(max_k>n/2) return inf_k(prices);
        int [][][]dp=new int[n][max_k+1][2];
        for(int i=0;i<n;i++){
            for(int k=max_k;k>=1;k--){
                 if(i-1==-1){
                dp[i][k][1]=-prices[0];
                continue;
            }
            dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
            dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
            }
           
        }
        return dp[n-1][max_k][0];
        
    }
  //k为inf的情况
    private int inf_k(int prices[]){
         int res=0;
        for(int i=1;i<prices.length;i++){
            res=Math.max(res,res+prices[i]-prices[i-1]);
        }
        return res;
    }
}

总结

到这里，所有的股票问题都过了一遍，我们可以看到诸如最开始的简单的两题，比如k=1或者k=inf的情况，我们可以通过暴力法直接求解，但是在这里想统一一下该类题的具体做法。我们便利用多维dp数组推导出了一般的形式，到最后为了省去边界情况的讨论，我们可以直接利用变量去代替这个dp数组.

事实上股票问题也不是那么的难，对吧！