动态规划：万变不离其宗，带你吃透股票系列问题

前言：

对于买卖股票问题而言，最关键的是我们对问题的处理方式（对于每一天而言，我们应该描述当天买入卖出还是只描述每天股票的只有或者不持有的状态呢？）我们应该描述每天股票是否持有的状态，因为每天持有股票的状态很好描述，只有持有和不持有这两种状态，但是如果选择描述在哪一天买入卖出类似这种状态，描述起来就很复杂了

一.买卖股票的最佳时机I（只能买一次）

题目描述（链接：力扣）

解题思路

我们使用动规五部曲对其进行分析：

1.数组下标及含义：在这里我们使用二维数组作为dp数组，为什么要使用二维数组呢？因为哪一天作为一个变量，每一天同时也会有两种状态：持有和不持有股票，因此我们使用dp[n][2]作为dp数组，n代表哪一天，2代表两种不同的状态，dp[][]代表当天某种状态下的最大利润。

2.递推公式：对于当前问题而言，只能买卖一次，对于每一天的状态而言dp[n][0]代表着持有股票：如果持有股票，则存在两种可能性：在前一天就持有，或者在当天买入，我们取其中利润的最大值，所以：dp[n][0]=max(dp[n-1][0],-prices[i]])（由于只能买卖一次，如果当天买入，意味着之前肯定没有买入，所以今天买入所获得的利润为-prices[i]），dp[n][1]代表着当天不持有股票的状态，同样存在两种组成的可能性：一种是由dp[n-1][0]继承而来，即前一天的状态就是未持有，今天的状态是前一天状态的延续，第二种是dp[n-1][0]+prices[i],即昨天是持有股票的状态，而今天把股票出售了，同样是两者取最大值。

3.初始化：我们由递推公式能得出的结论是：我们后一天的状态依赖于前一天的状态，所以第一天dp数组的正确性十分重要，dp[0][0]:代表第一天持有股票，所以其利润为：--prices[0] dp[0][1] 第一天不持有股票，所以其利润为：0

4.遍历顺序：既然是前面的推出后面的，所以遍历顺序自然是从前往后

5.打印dp数组：通过打印dp数组检查最后结果的正确性

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        //排除特殊情况
        if(prices.length==1){
            return 0;
        }
        //创建dp数组
        int[][]dp=new int[prices.length][2];
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][0],-prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[prices.length-1][1];
    }
}

二.买卖股票的最佳时机II（可以买无数次）

题目描述（链接：力扣）

解题思路

我们仍然使用动规五部曲进行分析：

1.数组下标和其代表的含义：每一天同时也会有两种状态：持有和不持有股票，因此我们使用dp[n][2]作为dp数组，n代表哪一天，2代表两种不同的状态，dp[][]代表当天某种状态下的最大利润。

2.递推公式：dp[n][0]代表当天持有股票，则有以下两种可能性：①延续前面的有股票的状态②前一天没有股票，但是今天新买了股票，我们仍然取两者的最大值：dp[n][0]=max(dp[n-1][0],dp[n-1][1]-prices[i]),dp[n][1]代表当天不持有股票，同样有两种可能性：前一天持有但是今天卖掉了，或者延续前一天没有股票的状态，状态方程为：dp[n][1]=max(dp[n-1][1],dp[n-1][1]+prices[i])

3.初始化：第一天持有股票：dp[0][0]=-prices[0] 第一天不持有股票： dp[0][1]=0

4.遍历顺序：与买卖股票最佳时机1一致，从前往后遍历

5.打印：通过打印数组，确认结果的正确性

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        //创建dp数组
        int[][]dp=new int[prices.length][2];
        //初始化
        dp[0][0]=-prices[0];
        //进行遍历
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][1]-prices[i],dp[i-1][0]);
            dp[i][1]=Math.max(dp[i-1][0]+prices[i],dp[i-1][1]);
        }
        return dp[prices.length-1][1];
    }
}

三.买卖股票的最佳时机III（只能买两次）

题目描述（链接：力扣）

解题思路

与前两个买卖股票II应用场景有所不同，这个题目对买卖股票添加了限制，限制买卖股票的次数（只允许买卖两次），看似与买卖股票一类似（买卖股票1只允许买卖一次），但是其场景却变化了很多：买卖股票I与II的区别只是在递推公式中的买入股票时的利润（I是dp[n][0]=max(dp[n-1][0],-prices[i]])，II是：dp[n][0]=max(dp[n-1][0],dp[n-1][1]-prices[i])），但是一旦限制股票只能买卖两次，其场景就复杂起来了，这时需要重新定义1.数组下标及其含义dp数组下标及其本身的含义：dp[n][0]:第n天没有进行任何操作：dp[n][1]:第一次持有股票 dp[n][2]:第一次不持有股票 dp[n][3]:第二次持有股票dp[n][4] 第二次不持有股票。

2.递推公式：每一种状态下的递推公式也有所不同，我们一一进行解释：dp[n][1]=max(dp[n-1][1]，dp[n-1][0]-prices[i]) (前一天第一次持有股票的状态或者前一天没有购买股票，今天刚购买)，dp[n][2]=max(dp[n-1][2],dp[n-1][1]+prices[i])（延续前一天第一次不持有的状态或者前一天持有，今天抛售）dp[n][3]=max(dp[n-1][3],dp[n-1][2]-prices[i])（延续前一天的第二次持有或者前一天没有持有，今天刚购买）dp[n][4]=max(dp[n-1][4]，dp[n-1][3]+prices[i])

3.初始化

dp[0][0]:第一天什么也没有操作，故结果为0 ,dp[0][1] 第一天第一次购买，利润是-prices[0] ,dp[0][2] 第一天出售股票，利润为0 dp[0][3] 第一天进行第二次购买股票，利润为（-prices[0]，第一天买入卖出再买入） dp[0][4]第二次进行抛售，利润同样为0

4.遍历顺序：与前面一致，都是从前往后遍历

5.打印查看结果正确性

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        //定义数组
        int[][]dp=new int[prices.length][5];

        //初始化
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[0][2]=0;
        dp[0][3]=-prices[0];
        dp[0][4]=0;
        //进行遍历
        for(int i=1;i<prices.length;++i){
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
            dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        return dp[prices.length-1][4];
    }
}

四.买卖股票的最佳时机IV（只能买k次）

题目描述（链接：力扣）

解题思路

解题思路与买卖股票III类似了：买卖股票III加上什么也不做的状态是定义了5种状态（未操作、第一次买入、第一次卖出、第二次买、第二次卖出），所以买卖股票IV相对于III而言，只有一点需要变化，那就是每一天的状态增加了：所以我们采用循环的方式，如下：其中k代表最多允许买卖的次数

for(int j=0;j<2*k-1;j+=2){
                dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
            }

我们直接给出完整的代码（与买卖股票III类似）

class Solution {
    public int maxProfit(int k, int[] prices) {
        //创建数组
        int[][]dp=new int[prices.length][2*k+1];
        //初始化
        for(int i=0;i<2*k;i+=2){
            dp[0][i+1]=-prices[0];
        }
        //遍历
        for(int i=1;i<prices.length;++i){
            for(int j=0;j<2*k-1;j+=2){
                dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
            }
        }
        return dp[prices.length-1][2*k];
    }
}

五.买卖股票的最佳时机V（含冷冻期）

题目描述（链接：力扣）

解题思路

与前面题目描述有所不同的是，这次的股票问题存在一个冷冻期，也正是这个冷冻期的存在，我们dp数组对应的下标及dp数组的含义都要发生一定的变化：我们之前只是将每一天的状态分为持有股票和不持有股票两种（不持有股票包含了今天刚卖掉股票和延续之前卖掉股票的状态乳癌），但是一旦引入冷冻期这个概念，我们就必须将卖出股票的状态进行细分：1.今天刚卖出股票2.处于冷冻期内（昨天卖出股票）3.之前卖出股票且不处于冷冻期内，所以总共的状态为4种，在此基础上加上持有股票的状态，使用动规五部曲对此进行分析：

①dp数组下标含义及其数组含义dp[i][0]:代表当前持有股票 dp[i][1]:代表当前保持卖出股票（最晚是前天卖出股票）；dp[i][2]代表今天刚卖出股票；dp[i][3]代表当前正处于冷冻期内

②递推公式：dp[i][0]=max(d[i-1][0]max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));(今天手中有股票，可能是延续前一天手中有股票的状态和昨天处于冷冻期内，今天买股票，或者昨天保持卖出股票的状态，今天买入股票) ；dp[i][1]=max(dp[i-1][3],dp[i-1][1])(保持前面的卖出股票状态或者昨天处于冷冻期，今天进入保持卖出股票) dp[i][2]=d[i][0]+prices[i](今天刚卖出股票，意味着前一天手里一定有股票，所以dp[i][2]只和前一天的dp[i-1][0]有关)；dp[i][3]=dp[i-1][2](今天处于冷冻期内意味着一定是昨天刚卖出股票，所以只由昨天的dp[i-1][2]决定)

③初始化：dp[0][0]=-prices[0](今天刚买股票) dp[0][1]=0(在第0天存在这个状态实际上是不合法的，我们可以将其理解为今天手中没有股票，所以初始化为0) dp[0][2]=0(今天买了股票之后直接买卖出了，所以利润为0) dp[0][3]=0(今天处于冷冻期的状态也是不合法的，我们将其初始化为0)

④遍历顺序：依然是从前面推出后面，所以遍历顺序也是从前往后

⑤ 打印数组：通过打印dp数组判断合法性

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        //创建数组
        int[][]dp=new int[prices.length][4];
        //进行初始化
        dp[0][0]=-prices[0];//0代表持有股票
        dp[0][1]=0;//1代表保持卖出股票
        dp[0][2]=0;//2表示卖出股票
        dp[0][3]=0;//3表示在冷冻期内
        //进行遍历循环
        for(int i=1;i<prices.length;++i){
         dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));
         dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);
         dp[i][2]=dp[i-1][0]+prices[i];
         dp[i][3]=dp[i-1][2];
        }
        //返回最后卖出股票中的最大值
        return Math.max(dp[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));
    }
}

六.买卖股票的最佳时机VI（含手续费）

题目描述（链接：力扣）

解题思路

本题与买卖股票II基本一致，唯一的区别在于我们在卖出股票的时候需要加上手续费，所以体现在代码上就是递推公式发生了变化：

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

其他与买卖股票II完全一致：我们直接给出代码.

代码实现

class Solution {
    public int maxProfit(int[] prices, int fee) {
        //定义dp数组
        int[][]dp=new int[prices.length][2];
        //初始化
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        //进行遍历
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][1]-prices[i],dp[i-1][0]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
        }
        return dp[prices.length-1][1];
    }
}