前言

今天王子与大家继续分享LeeCode上有关如何买卖股票获取最高利润的题目。

本文作为补充文章，对更复杂的题目进行解答，如果还没有阅读上篇文章，希望小伙伴们先去看一下上篇文章：详解股票买卖算法的最优解(一)，有助于理解。

上篇文章我们讲解了根据状态机、状态转移方程思考问题，解决了4道有关股票买卖的题目，今天我们再来看两道复杂的题目。

请看下面的题目：

 这道题目包含了几乎所有的情况，下面我们来进行分析。

第一题，k=2,即最多交易两次

k=2和之前题目就不一样了，之前是不需要考虑k的情况的，但是这道题是要把k放到考虑范围内的，状态转移方程不能化简，就是最开始分析的样子，但稍微有些不同的是k值什么时候加一，之前的文章我们说当每次buy的时候k加一，为了后文更好理解我们现在把k加一这一操作放到sell操作后，也就是说卖出后才算一次完整的交易，k才会加一，所以转移方程如下：

dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i]);
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);

如果按照之前的解题方法，很容易会写成下边这种代码：

int k=2;
int[][][] dp=new int[n][k+1][2];
for(int i=0;i<n;i++){
  if(i=0){处理特殊值};
  dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i]);
  dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);  
}
return dp[n-1][2][0];

但这样是错误的，还记得我们前文提到的穷举框架吗，穷举的是所有的状态，之前我们不用考虑k，但是这道题目考虑了k就要对k再进行穷举。

我们先逐一分析特殊情况，有助于理解：

dp[i][0][0]：表示第i天交易了0次时的空仓状态
dp[i][0][1]：表示第i天交易了0次时的持有状态
dp[i][1][0]：表示第i天交易了1次时的空仓状态
dp[i][1][1]：表示第i天交易了1次时的持有状态
dp[i][2][0]：表示第i天交易了2次时的空仓状态
dp[i][2][1]：表示第i天交易了2次时的持仓状态（也就是第三次交易已经买入了，实际不存在这种情况，交易了两次后不能再交易，所以一定是空仓状态）

对于上边的情况我们再做一个分析：

dp[i][0][0]：对应于初始状态，第i天0次交易，空仓状态，利润一定是0
dp[i][0][1]和dp[i][1][0] 这两个是一对，对应的就是第一次买入、第一次卖出（卖出的时候才会增加交易次数）。
dp[i][1][1]和dp[i][2][0] 这两个也是一对，对应的就是第二次买入、第二次卖出。
dp[i][2][1]对应的是第三次的买入，因为我们限定了买入次数最多为两次，所以这种情况不存在。

接下来我们再详细分析一下第一次买卖的状态转移方程

第一次买入：从初始状态转换而来，或者第一次买入后保持不动
dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])

第一次卖出：从第一次买入转换而来，或者第一次卖出后保持不动
dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][0][1]+prices[i])

第二次买卖的状态转移方程：

第二次买入：从第一次卖出转换而来，或者第二次买入后保持不动
dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][1][0]-prices[i])


第二次卖出：从第二次买入转换而来，或者第二次卖出后保持不动
dp[i][2][0] = max(dp[i-1][2][0],dp[i-1][1][1]+prices[i])

我们把第一次买卖、第二次买卖的转移方程合到一起，就得到了最后的结果。
同时还要处理特殊情况的特殊值。
最后求的利润最大值就保存在 dp[n-1][0][0]、dp[n-1][1][0]、dp[n-1][2][0]中，我们求出这几个值的max再返回就可以了。

为什么我们考虑最大利润要把dp[n-1][0][0]这种情况算上呢，因为如果股市价格类似[5,4,3,2,1]，这种一直下跌的情况，不交易的利润是0，而交易了一定是亏损的。

直接看代码

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int max=0;
        //定义三维数组，第i天、交易了多少次、当前的买卖状态
        int[][][] dp = new int[n][3][2];
        for(int i=0;i<n;i++) {
          for(int k=0;k<=2;k++){
            if(i==0){
                dp[i][k][0]=0;
                dp[i][k][1]=-prices[i];
                continue;
            };
            dp[i][k][1] = Math.max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);
            if(k==0){
                dp[i][k][0] = dp[i-1][k][0];
            }else{
                dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i]);
            }
          } 
        }
        for(int k=0;k<=2;k++){
            if(max<dp[n-1][k][0]){
                max=dp[n-1][k][0];
            }
        }
        //返回最大值
        return max;
    }

有了状态转移方程的概念，想看懂上边的代码其实不难，但是如果把变量名全都改成a,b,c,d，我估计大多数人都会看着你的代码脑壳生疼。

好了，我们再来看下一题。

第二题，k=任何值，即交易次数限制是动态获取的

这题和 k = 2 没啥区别，解法基本相同。但是需要考虑k值的取值范围，k值不能无限大。想一想，k值也就是交易次数有什么限制呢？

一次交易由买入和卖出构成，至少需要两天。所以说有效的限制次数 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。

所以可以套用之前的k=+infinity的算法

最终结果如下：

public int maxProfit(int max_k, int[] prices) {
        if(prices.length==0){
            return 0;
        }
        int n = prices.length;
        if(max_k>n/2){
            return maxProfit(prices);
        }
        int max=0;
        //定义三维数组，第i天、交易了多少次、当前的买卖状态
        int[][][] dp = new int[n][max_k+1][2];
        for(int i=0;i<n;i++) {
          for(int k=0;k<=max_k;k++){
            if(i==0){
                dp[i][k][0]=0;
                dp[i][k][1]=-prices[i];
                continue;
            };
            dp[i][k][1] = Math.max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);
            if(k==0){
                dp[i][k][0] = dp[i-1][k][0];
            }else{
                dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i]);
            }
          } 
        }
        for(int k=0;k<=max_k;k++){
            if(max<dp[n-1][k][0]){
                max=dp[n-1][k][0];
            }
        }
        //返回最大值
        return max;
    }

    public int maxProfit(int[] prices) {
        int n=prices.length;
        int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            int temp=dp_i_0;
            dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1=Math.max(dp_i_1,temp-prices[i]);
        }
        return dp_i_0;
    } 

至此，算上上篇文章的4道题目，一共6到关于股票买卖的问题已经全部解决。

总结

好了，关于股票买卖算法的最优解系列就告一段落。

这类题型的解题思路就是引入了状态转移方程的概念，现在我们一起弄懂了这种解题思路，是不是还有一点小成就感呢。

解决这类问题的关键就是确认有几种选择，确定有几种状态，设定状态转移方程，处理特殊情况的值。之后就是套用进代码，解决问题。

希望大家再做算法题的时候脑子里能回忆起这种框架的解题思路。

如果觉得文章内容对你有所启发，希望点个赞，我们后续还会有很多内容与大家分享，不见不散。

往期文章推荐：

中间件专辑：

什么是消息中间件？主要作用是什么？

常见的消息中间件有哪些？你们是怎么进行技术选型的？

你懂RocketMQ 的架构原理吗？

聊一聊RocketMQ的注册中心NameServer

Broker的主从架构是怎么实现的？

算法专辑：

和同事谈谈Flood Fill 算法

详解股票买卖算法的最优解(一)