dp[i][0]表示第 i 天持有股票的最大利润，dp[i][1]表示第 i 天不持有股票的最大利润，那么最终问题的解就是max(dp[len – 1][0], dp[len – 1][1])；（实际上这里的解因该是dp[len – 1][1]，因为你最后一天一定是一个股票不持有的状态，才是利润最大的！）

1.2、递推公式

分析：

dp[i][0]表示第 i 天持有股票，有两种情况：

1. 第 i 天才买的股票，所以第 i 天持有股票 –> -prices[i]。（这里直接是-prices[i]，是因为本题中买卖股票的交易只有一次，不存在i – 1天前交易获利了今天继续买股票的情况，也就是dp[i – 1][1] -prices[i]）

2. 前 i – 1 天中的某一天买的股票，所以第 i 天持有 –> dp[i – 1][0]。

dp[i][1]表示第i天不持有股票，有两种情况：

1. 之前一直持有股票，第 i 天才卖出股票，所以第 i 天不持有股票 –> dp[i – 1][0] + prices[i]。（前i – 1天持有股票的最大利润 + 第 i 天卖出所赚的利润）；

2. 前 i – 1天中的某一天卖出了，所以第 i 天不持有股票 –> dp[i – 1][1]。

状态转移方程：

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]);

1.3、遍历顺序

由上面的递推公式可以知道，第 i 天的状态是由前i – 1天的状态推导而来，所以是顺序遍历；

1.4、初始化

分析：

由递推公式中可以看出，每一个状态都需要依赖于前面的一个状态推导而来，那么一直往回推，推导根源就是dp[0][0]和dp[0][1]；

dp[0][0]表示第0天持有股票，那么就是第一个股票的价钱；

dp[0][1]表示都0天不持有股票，那么就是0；

初始化：

dp[0][0] = prices[0];

dp[0][1] = 0;

1.5、解题代码

class Solution {
    public int maxProfit(int[] prices) {
        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 ——>交易到结束

题目描述：

题目来源：122. 买卖股票的最佳时机 II

2.1、分析

与买股票的最佳时机I，唯一的差别就是本题买卖股票的次数可以是多次，那么不同点就是在状态转移方程上。

实际上在那道题中，我就已经说明了，状态转移方程的区别，如果不太理解可以翻回去看看；

递推公式如下：

第i天持有股票：

dp[i][0] = Math.max(dp[i – 1][0], dp[i – 1][1] – prices[i]);

第i天不持有股票：

dp[i][1] = Math.max(dp[i – 1][1], dp[i – 1][0] + prices[i]);

2.2、解题代码

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];//持有
        dp[0][1] = 0;//不持有
        for(int i = 1; i < prices.length; i++) {
            //第i天持有股票
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            //第i天不持有股票
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.length - 1][1];
    }
}

三、买股票的最佳时机III ——>指定次数交易（2次）

题目描述：

题目来源：123. 买卖股票的最佳时机 III

3.1、dp定义

与前两道题唯一的区别是，本题买卖股票的交易只能进行两次，那么这里要定义的状态就需要多一些了；（为什么会像下方这样定义，在第一题中有详细分析）

dp[0][0]：什么都不操作。（这个状态可有可无，只是为了后面递推公式更加完整）；

dp[0][1]：第一次持有股票。

dp[0][2]：第一次不持有股票。

dp[0][3]：第二次持有股票。

dp[0][4]：第二次不持有股票。

3.2、递推公式

分析：

dp[i][0]：什么都不操作，那就可以表示为前一天的状态 –> dp[i – 1][0]。

dp[i][1]：可以是前i – 1就已经持有了第一次的股票 –> dp[i – 1][1]；也可以是今天才第一次买股票（那么前i – 1天一定是什么都没有做） –> dp[i – 1][0] – prices[i]。

dp[i][2]：可以是前i – 1天不持有第一次的股票 –> dp[i – 1][2]；也可以是前i – 1天持有第一次的股票，在第i天的时候才卖出 –> dp[i – 1][1] + prices[i]；

dp[i][3]：可以是前i – 1天就持有了第二次的股票 –> dp[i – 1][3]；也可以是前i – 1天不持有第二的股票，第i天才持有（那么一定是前i – 1天中的某一天已经不持有第一次的股票了） –> dp[i – 1][2] – prices[i]；

dp[i][4]：可以是前i – 1天不持有第二次的股票 –> dp[i – 1][4]；也可以是前i – 1天持有第二次的股票，接着第i天卖出第二次的股票 –> dp[i – 1][3] + prices[i]；

状态转移方程：

dp[i][0] = dp[i – 1][0];

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]);

3.3、遍历顺序

由上面的递推公式可以知道，第 i 天的状态是由前i – 1天的状态推导而来，所以是顺序遍历；

3.4、初始化

分析：

根据状态转移方程可以看出，每一个状态都是由前一个状态推出来的，一直往前推，也就是说，我们应该要初始化dp[0][0~4]；

注意：这里需要提前知道的一点是，题目中没有明确规定，“股票不能当天买入天卖出”，实际上，“这天什么都不干” 就等同于 “股票当天买入当天卖出”，她两的利润都是0，所以可以认为是一样的。（这对理解初始化至关重要）

解释：

dp[0][0]：第一天什么都不做，那么最大利润一定是0；

dp[0][1]：第一天第一次持有股票，那么一定是是第一天买入的的股票，也就是-prices[0]；

dp[0][2]：第一天第一次不持有股票，就是第一天什么都没做，也可以理解为“股票当天买入当天卖出”，最大利润就是0；

dp[0][3]：第一天第二次持有股票，可以理解为“这一天已经进行了一次买卖股票”，接着，又买了一次股票，所以利润就是-prices[0]；

dp[0][4]：第一天第二次不持有股票，可以理解为“这一天已经进行了一次买卖股票”，接着，并没有做任何操作，那么最大利润还是0；

初始化：

dp[0][0] = 0;//不操作

dp[0][1] = -prices[0];//第一次持有

dp[0][2] = 0;//第一次不持有

dp[0][3] = -prices[0];//第二次持有

dp[0][4] = 0;//第二次不持

3.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][0] = dp[i - 1][0];
            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次）

题目描述：

题目来源：188. 买卖股票的最佳时机 IV

4.1、分析

本题就是 “买卖股票的最佳时机III” 的升级版，买卖股票的次数由2次变成了k次。

不难看出，本题虽有有了更多的状态，但dp数组的含义，状态转移方程，初始化是一样的；

因此，如果你理解了 “买卖股票的最佳时机III” 的题解，这道题是可以直接秒杀的；

4.2、解题代码

class Solution {
    public int maxProfit(int k, int[] prices) {
        int ans = 2 * k + 1;
        int[][] dp = new int[prices.length][ans];
        //初始化
        for(int i = 0; i < ans; i++) {
            dp[0][i] = i % 2 == 0 ? 0 : -prices[0];
        }
        //遍历
        for(int i = 1; i < prices.length; i++) {
            dp[i][0] = dp[i - 1][0];
            for(int j = 1; j < ans; j++) {
                if(j % 2 == 1) { //买入
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                }
            }
        }
        return dp[prices.length - 1][ans - 1];
    }
}

五、最佳买卖股票时机含冷冻期 ——>交易到结束（含冷冻期）

题目描述：

题目来源：309. 最佳买卖股票时机含冷冻期

5.1、dp定义

分析：

以往的题我们都是拆分成 [持股，不持股] 两种状态，本题多了一个冷冻期状态，冷冻期是要求前一天必须为“当天卖出”状态，而我们的“不持股”状态（它表示从某一天卖出开始一直不持股持续到今天，具体是那一天开始不持股不知道！）无法准确描述它，因此，我们需要将“不持股”这个状态拆分成 “冷冻期后的不持股” 和 “当天卖出不持股”这两种状态。

dp定义：

dp[i][0]：持股时所含的最大利润；

dp[i][1]：冷冻期后的不持股 时所含的最大利润；

dp[i][2]：当天卖出股票 时所含的最大利润；

dp[i][3]：冷冻期 时所含的最大利润；

5.2、递推公式

分析：

dp[i][0]：持股有三种情况：

1.前i – 1天一直持股，今天延续这个状态；2.冷冻期后不持股，然后当天买入股票；3.前一天是冷冻期，今天买入股票。

dp[i][1]：冷冻期后的不持股 有两种情况：

1.前i – 1天一直是冷冻期后的不持股状态，今天延续这个状态；2.前一天就是冷冻期，今天就是冷冻期后的不持股状态。

dp[i][2]：当天卖出股票 只有一种情况：

1.前i – 1天持股，今天卖出。

dp[i][3]：冷冻期 只有一种情况：

1.前一天卖出股票。

状态转移方程：

dp[i][0] = Math.max(dp[i – 1][0], Math.max(dp[i – 1][1] – prices[i], dp[i – 1][3] – 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];

5.3、遍历顺序

由上面的递推公式可以知道，第 i 天的状态是由前i – 1天的状态推导而来，所以是顺序遍历；

5.4、初始化

Ps：这里分析思路和 “买卖股票的最佳时机III的方法是一样的”；

dp[0][0] = -prices[0];//持股

dp[0][1] = 0;//冷冻期后的不持股

dp[0][2] = 0;//当天卖出股票

dp[0][3] = 0;//冷冻期

5.5、解题代码

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][4];
        dp[0][0] = -prices[0];//持股
        dp[0][1] = 0;//冷冻期后的不持股
        dp[0][2] = 0;//当天卖出股票
        dp[0][3] = 0;//冷冻期
        for(int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1] - prices[i], dp[i - 1][3] - 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[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
    }
}

六、买卖股票的最佳时机含手续费 ——>交易到结束（含手续费）

题目描述：

题目来源：714. 买卖股票的最佳时机含手续费

6.1、分析

此题可以说是和 “买卖股票的最佳时机II” 几乎一模一样……

唯一的区别就是本题在每次买卖股票完后，都需要减掉一个手续费~

因此，如果你理解了 “买卖股票的最佳时机II” 的题解，这道题是可以直接秒杀的；

6.2、解题代码

class Solution {
    public int maxProfit(int[] prices, int fee) {
        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], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[prices.length - 1][1];
    }
}