DP5

2020-05-21

DP5

股票问题全攻略：

在最开始的几道股票问题中，或许我们可以不通过DP来求解，也是很好的方法，那么我将列举出非DP套路，例如暴力法，贪心….. 但是到了后面的题目，我希望能够总结出一套DP的体系。能够将DP灵活的运用到这几道DP问题中

121、买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

首先第一题的关键词就是只能完成一笔交易
我们利用暴力法，先不管只能交易一次，而是枚举出所有的交易情况，然后取最大值.注意要过滤掉负数

class Solution {
    public int maxProfit(int[] prices) {
       int cur=0,res=0;
        for(int i=1;i<prices.length;i++){
            //过滤掉负数，卖出价格需要大于买入价格
            cur=Math.max(0,cur+prices[i]-prices[i-1]);
            res=Math.max(res,cur);
        }
        return res;
        
    }
}

接下来我们利用DP的思路，这里的思路也很简单，我们只需要考虑获得最大利润时是持有股票还是卖出股票，即我们可以利用两个dp数组，与之前的打家劫舍中的一题很类似.

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、买卖股票的最佳时机2 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

第2题的关键词就是可以进行无数次交易(这里的无数次是指尽可能多的交易)
那么这样我们就可以利用贪心的思路，如果交易的利润是正的话，我们可以一直更新结果

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

与第一题类似，在这里提供DP的做法

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int hold=-prices[0];
        int sell=0;
        for(int i=1;i<prices.length;i++){
            sell=Math.max(sell,hold+prices[i]);
          //这里可以进行多次交易
            hold=Math.max(hold,sell-prices[i]);
        }
        return Math.max(sell,hold);
    }
}

123、买卖股票的最佳时机3 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

本题的关键点是最多可以完成两笔交易
有一个可行的想法是我们直接列出所有情况

class Solution {
    public int maxProfit(int[] prices) {
          if(prices.length<2) return 0;
      //第一次不持有股票，第一次持有股票
         int firstSell=0,firstHold=-prices[0];
      //第二次不持有股票，第二次持有股票
         int secondSell=0,secondHold=-prices[0];
        for(int i=1;i<prices.length;i++){
          //保留或者卖出
             firstSell=Math.max(firstSell,firstHold+prices[i]);
          //保留或者第一次买
               firstHold=Math.max(firstHold,-prices[i]);
            //保留状态或者在前一天没有股票，然后今天买入
            secondHold=Math.max(secondHold,firstSell-prices[i]);
          //保留状态或者今天卖出
               secondSell=Math.max(secondSell,secondHold+prices[i]);
               
        }
      //第二次买入的利润影响着第二次卖出的利润，即第二次卖出的利润就是最终结果
        return secondSell;
    }
}

188、买卖股票的最佳时机4 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

本题就是第三题的一般形式，即最多可以进行k笔交易

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k==0||prices.length==0) return 0;
         if(k>=prices.length/2) return greedy(prices);
         int []buy=new int[k];
        int [] sell=new int[k];
        for(int i=0;i<k;i++){
            buy[i]=-prices[0];
            sell[i]=0;
        }
      //否则的话就是常规思路
        for(int i=0;i<prices.length;i++){
            buy[0]=Math.max(buy[0],-prices[i]);
            sell[0]=Math.max(sell[0],buy[0]+prices[i]);
            for(int j=1;j<k;j++){
              //在第k笔交易，如果是持有操作时，与第k-1批的 不持有有关
                buy[j]=Math.max(buy[j],sell[j-1]-prices[i]);
              //在第k笔交易时，不持有操作与当前持有操作有关
                sell[j]=Math.max(sell[j],buy[j]+prices[i]);
            }
        }
        return sell[k-1];
    }
  //当k很大时，我们直接利用贪心思想，即与第二种情况一样
    private int greedy(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;
    }
}