买卖股票最佳时机系列问题的思想———动态规划

买卖股票的最佳时机1

这是该系列题目的最基础的一题,题目来源于121. 买卖股票的最佳时机 – 力扣（LeetCode）.

• 由于这道题目只能选择一天买入,并且在一天卖出所得的最大利润,而且不能够进行多笔交易,所以可以认为这次的股票只能进行一次交易,也就是一次利润计算.我们可以使用暴力法进行求解.

• public class Solution121 {
      public int maxProfit(int[] prices){
          int i=0,j=0;
          int profit=0;
          for(i=0;i< prices.length;i++){
              for(j=i+1;j<prices.length;j++){
                  if(prices[j]-prices[i]>profit){
                      profit=prices[j]-prices[i];
                  }
              }
          }
          return profit;
      }
  }

  但是暴力法的时间复杂度高达n^2,所以我们使用下列一次循环的方法

• 接着我们使用动态规划的思想来看这道题,我们可以先定义f(n):f(n)是前n天的最大利润.然后列状态转换方程.f(i) = max(f(i-1),prices[i]-min(prices[0:i])——-(0:i是指从0到i的最小买入价格).

• 我们可以先遍历一遍数组,找到最小的价格,之后用最小的价格来对比其他天数的价格与最小价格的差值,从而找到从哪天买入,哪天卖出的利润是最高的

• public class Solution121 {
      public int maxProfit(int[] prices){
          int i=0;
          int minProfit=Integer.MAX_VALUE;
          int maxProfit=0;
          for(;i<prices.length;i++){
              //寻找最小的一天的股票价格
              if(prices[i]<minProfit){
                  minProfit=prices[i];
              }
              //寻找在已知的最小股价后的最大利润
              else{
                  maxProfit= Math.max(maxProfit,prices[i]-minProfit);
              }
          }
          return maxProfit;
      }
  }
  

  这种方法通过一次遍历获得最大利润,时间复杂度仅仅为n,所以并不会超时.

买卖股票的最佳时机2

接下来我们来看这道题的进阶,你可以进行多次交易,但是你的手中至多持有一张股票,求你能获得的最大利润,该题来源于122. 买卖股票的最佳时机 II – 力扣（LeetCode）

• 首先该题也不能进行多笔交易,我们可以先定义dp[i][0]表示在第i天没有持有股票时候的利润,而dp[i][1]可以表示在第i天持有一支股票时候的利润.
• 对于dp[i][0]来说,可以分为两种情况,第一种情况就是dp[i-1][0],表示前一天中也没有持有股票,第二种情况就是dp[i-1][1],在前一天中是拥有一张股票的,所以dp[i][0]=dp[i-1][1]+prices[i].
• 考虑到利润最大化,因此有如下的转移方程:dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
• 而对于dp[i][1]来说,也可以分为两种情况,第一种情况是dp[i-1][1],表示在前一天中已经持有了一张股票,第二种情况是dp[i-1][0],在前一天中没有股票,所以需要在今天买入,因此dp[i][1]=dp[i-1][0]-prices[i].
• 考虑到利润最大化,可以列出如下的转换方程:dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]).
• 所以照这样递归下去,始终dp[i][0]>dp[i][1],又因为dp[0][0]=0,dp[0][1]=-prices[0].

• public class Solution122 {
      public int maxProfit(int[] prices) {
          int n=prices.length;
          //创建二维数组用于记录股票利润
          int[][] dp=new int[n][2];
          //开始时候持有股票只能买进第一天的股票,或者选择不买进
          dp[0][0]=0;
          dp[0][1]=-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]);
              dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
          }
          //由于卖出利润始终大于买入后的利润
          return dp[n-1][0];
      }
  }
  

  买卖股票的最佳时机3

这道题目中的条件是在2的基础上增加一个至多只能交易两笔,所以要在2的基础上增加一个约束条件,题目来源于123. 买卖股票的最佳时机 III – 力扣（LeetCode）

• 关于该题的动态规划,我们可以认为有着五类情况.
• 第一类情况是没有买入也没有卖出,由于此时无论股票每一天是多少钱利润都是0,所以转换方程是0.
• 第二类情况是仅仅买入一次,此时利润我们定义为buy1,即buy1=-prices[i]
• 第三类情况就是买入了一次,也卖出了一次,我们定义为sell1,即sell1=buy1’+prices[i],其中buy1’也就是i-1买入的股票价格
• 第四类情况就是买卖了一次,又买了第二次,我们定义为buy2,即buy2=sell1′-prices[i],其中sell’也就是上一次买卖所获得的利润
• 第五类情况就是买卖了两次,我们定义为sell2,即sell2=buy2’+prices[i],其中buy2’就是上一次buy2的利润
• 列出上列各类情况的状态转换方程
• buy1=max(buy1,-prices[i])
• sell1=max(sell1,buy1+prices[i])
• buy2=max(buy2,sell1-prices[i])
• sell2=max(sell2,buy2+prices[i])

• public class Solution123 {
      public static int maxProfit(int[] prices) {
          int buy1=-prices[0],buy2=-prices[0],sell1=0,sell2=0;
          for(int i=1;i<prices.length;i++){
              buy1=Math.max(buy1,-prices[i]);
              sell1=Math.max(sell1,buy1+prices[i]);
              buy2=Math.max(buy2,sell1-prices[i]);
              sell2=Math.max(sell2,buy2+prices[i]);
          }
          return sell2;
      }
  }

 买卖股票的最佳时机4

这道题目中的条件是在2的基础上从至多两次变为了至多k次,题目来源于188. 买卖股票的最佳时机 IV – 力扣（LeetCode）

• 对于这道题目,我们可以将问题结果抽象为两种情况,第一种情况就是买入的情况,第二种情况是卖出的情况,于是我们可以定义buy[i]与sell[i],而又有着至多几次交易的限制,于是我们可以为两类情况加上限制条件.最终我们定义出来的最优子结构就是buy[i][j]和sell[i][j].
• 对于其中的buy[i][j]来说,当你在第i天的时候手中持有股票只有两种情况,第一类情况是昨天已经将股票买入,第二种情况是今天刚刚把股票买入,所以buy[i][j]的状态转换方程是Math.max(buy[i-1][j],sell[i-1][j]-prices[i]).
• 对于其中的sell[i][j]来说,当你在第i天的时候手中没有股票也是由两种情况,第一类情况是昨天已经将股票卖出,今天没有买入,第二种情况是昨天没有将股票卖出,而是在今天将股票卖出,所以sell[i][j]的状态转换方程为Math.max(sell[i-1][j],buy[i-1][j-1]+prices[i])注:j-1是因为当今天卖出去彩票后,昨天的交易已经是上一次交易了.
• 关于buy和sell的边界,因为在0此交易,也就是没有进行交易的时候,buy[0][0]=-prices[i],而sell[0][0]=0,而在交易多次后,还是在第1天的情况是不存在的,于是将这些情况定义为不可能的清苦那个,用负无穷大来替代

• public class Solution188 {
      public static int maxProfit(int k, int[] prices) {
          int n=prices.length;
          int[][] buy=new int[n][k+1];
          int[][] sell=new int[n][k+1];
  
          buy[0][0]=-prices[0];
          sell[0][0]=0;
          for (int i = 1; i <= k; i++) {
              buy[0][i]=sell[0][i]=Integer.MIN_VALUE/2;
          }
          int j=0;
          for(int i=1;i<n;i++){
             buy[i][0]=Math.max(buy[i-1][0],sell[i-1][0]-prices[i]);
             for(j=1;j<=k;j++){
                 buy[i][j]=Math.max(buy[i-1][j],sell[i-1][j]-prices[i]);
                 sell[i][j]=Math.max(sell[i-1][j],buy[i-1][j-1]+prices[i]);
             }
          }
          int maxProfit=0;
          for(int i=0;i<=k;i++){
              if(sell[n-1][i]>maxProfit){
                  maxProfit=sell[n-1][i];
              }
          }
          return maxProfit;
      }