Day43——Dp专题

红太狼 2024-03-30 10:01 54阅读 0赞

#### 文章目录 ####

*   *  股票问题篇
     *   *  21、买卖股票的最佳时机
         *  22、买卖股票的最佳时机II
         *  23、买卖股票的最佳时机Ⅲ
         *  24、买卖股票的最佳时机Ⅳ
         *  25、最佳买卖股票时机含冷冻期
         *  26、买卖股票的最佳时机含手续费
     *  股票问题总结篇
     *   *

--------------------

### 股票问题篇 ###

#### 21、买卖股票的最佳时机 ####

[力扣题目链接][Link 1]

**动态规划**

定义二维数组：`dp[n][2]`

**状态表示**：

`dp[i][0]`表示第`i`天没有持有股票所得最大现金（利润）

`dp[i][1]`表示第`i`天持有股票所得最大现金（利润）

**状态计算**：

*  `dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]`
 *  `dp[i][1] = max(dp[i - 1][1], -prices[i])`
    
     *  第`i-1`天就持有股票，那么就保持现状（不买入），所得现金就是昨天持有股票的所得现金 即：`dp[i - 1][1]`
     *  第`i`天买入股票（买入），所得现金就是买入今天的股票后所得现金即：`-prices[i]`

**初始化**：

*  `f[0][1] = -prices[0];`
 *  `f[0][0] = 0;`

结果返回：`f[n - 1][0]`：最后一天不持有股票的最大利润（要么买了股票然后卖出去赚钱了，要么没买即为0）

**Code**

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if(prices==null||prices.length==0){
        
                return 0;
            }
            int n = prices.length;
            int[][] dp = new int[n][2];
            dp[0][1] = -prices[0];
            dp[0][0] = 0;
            for(int i = 1; i < n; 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],-prices[i]);
            }
            return dp[n - 1][0];
        }
    }

#### 22、买卖股票的最佳时机II ####

[力扣题目链接][Link 2]

本题和题I的唯一区别本题股票可以买卖多次了（注意只有一只股票，所以再次购买前要出售掉之前的股票）!

**动态规划**

定义二维数组：`dp[n][2]`

**状态表示**：

`dp[i][0]`表示第`i`天没有持有股票所得最大现金（利润）

`dp[i][1]`表示第`i`天持有股票所得最大现金（利润）

**状态计算**：

*  `dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]` ——Ⅱ
 *  `dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]-prices[i])`——Ⅰ
    
     *  第`i-1`天就持有股票，那么就保持现状（不买入），所得现金就是昨天持有股票的所得现金 即：`dp[i - 1][1]`
     *  第`i`天买入股票（买入），所得现金就是买入今天的股票后所得现金即：`dp[i - 1][0]-prices[i])`

**初始化**：

*  `f[0][1] = -prices[0];`
 *  `f[0][0] = 0;`

结果返回：`f[n - 1][0]`：最后一天不持有股票的最大利润（要么买了股票然后卖出去赚钱了，要么没买即为0）

**对比Ⅰ和Ⅱ买卖股票的最佳时机**

`dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]-prices[i])`

`dp[i][1] = max(dp[i - 1][1], -prices[i])`

原因就是`II`可以买卖多次就要积累前面赚到的最大利润，而`I`只能买卖一次，刚刚买入时利润必定是`-prices[i]`

**Code**

**二维数组**

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if(prices==null||prices.length==0){
        
                return 0;
            }
            int n = prices.length;
            int[][] dp = new int[n][2];
            dp[0][1] = -prices[0];
            dp[0][0] = 0;
            for(int i = 1; i < n; 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];
        }
    }

**一维数组**

// 优化空间
    class Solution {
        
        public int maxProfit(int[] prices) {
        
            int[] dp = new int[2];
            dp[1] = -prices[0];
            dp[0] = 0;
            for(int i = 1; i < prices.length; i++){
        
                dp[1] = Math.max(dp[1], dp[0] - prices[i]);
                dp[0] = Math.max(dp[0], dp[1] + prices[i]);
            }
            return dp[0];
        }
    }

#### 23、买卖股票的最佳时机Ⅲ ####

[力扣题目链接][Link 3]

**动规五部曲**

*  **确定dp数组以及下标含义**

1.  没有操作
2.  第一次买入
3.  第一次卖出
4.  第二次买入
5.  第二次卖出

`dp[i`\]\[j\]中 i表示第i天，j为 \[0 - 4\] 五个状态，`dp[i][j]`表示第i天状态j所剩最大现金

*  **确定递推公式**

`dp[i][1]`，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，有可能i-1天买的股票

达到`dp[i`\]\[1\]状态，有两个具体操作：

*  操作一：第i天买入股票了，那么`dp[i][1] = dp[i-1][0] - prices[i]`
 *  操作二：第i天没有操作，而是沿用前一天买入的状态，即：`dp[i][1] = dp[i - 1][1]`

同理`dp[i][2]`也有两个操作：

*  操作一：第i天卖出股票了，那么`dp[i][2] = dp[i - 1][1] + prices[i]`
 *  操作二：第i天没有操作，沿用前一天卖出股票的状态，即：`dp[i][2] = dp[i - 1][2]`

**每次dp第一种是上一个状态的延续，还有一种为本次的改变（买入或卖出）**

同理可推出剩下状态部分：

`dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);`

`dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);`

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

*  **dp数组初始化**

第0天没有操作，这个最容易想到，就是0，即：`dp[0][0] = 0;`

第0天做第一次买入的操作，`dp[0][1] = -prices[0];`

**存在一种情况当天买，当天卖**

*  第一次持有或第二次持有

dp[0][1] = -prices[0];
      dp[0][3] = -prices[0];

*  第一次不持有或第二次不持有

dp[0][2] = 0;
    dp[0][4] = 0;

*  **确定遍历顺序**

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp\[i\]，依靠`dp[i - 1]`的数值。

*  **举例并推导dp数组**

![image-20221212220237134][]

现在最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。

所以最终最大利润是`dp[n-1][4]`

**Code**

**二维**

class Solution {
        
        public int maxProfit(int[] prices) {
        
            int n = prices.length;
            if(prices==null||n==0){
        
                return 0;
            }
            int[][] dp = new int[n][5];
            dp[0][1] = -prices[0];
            dp[0][3] = -prices[0];
            for(int i = 1; i < n; i++){
        
                dp[i][1] = Math.max(dp[i-1][1],-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[n-1][4];
        }
    }

**一维**

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

#### 24、买卖股票的最佳时机Ⅳ ####

[力扣题目链接][Link 4]

本题与Ⅲ的区别在于买卖股票k次，就是将Ⅲ抽象出来

**动规五部曲**

*  **确定dp数组以及下标的含义**

使用二维数组 `dp[i][j]` ：第i天的状态为j，所剩下的最大现金是`dp[i][j]`

j的状态表示为：

*  0 表示不操作
 *  1 第一次买入
 *  2 第一次卖出
 *  3 第二次买入
 *  4 第二次卖出
 *  j+1就是买入，j+2就是卖出

**除了0以外，偶数就是卖出，奇数就是买入**。

*  **确定递推公式**

dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
      dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);

*  **dp数组初始化**

`dp[0`\]\[j\]当j为奇数的时候都初始化为 -prices\[0\],j为偶数的时候都初始化为0

*  **确定遍历顺序**

一定是从前向后遍历，因为dp\[i\]，依靠dp\[i - 1\]的数值。

*  **举例并推导dp数组**

![image-20221214195453126][]

最后一次卖出，一定是利润最大的，`dp[prices.size() - 1][2 * k]`即红色部分就是最后求解

**Code**

**二维**：股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作

class Solution {
        
        public int maxProfit(int k, int[] prices) {
        
            if(prices==null||prices.length==0){
        
                return 0;
            }
            int n = prices.length;
            int[][] dp = new int[n][2*k+1];
            for(int j = 1;j < 2*k; j += 2){
        
                dp[0][j] = -prices[0];
            }
            for(int i = 1;i < n;i++){
        
                for(int j = 0;j < 2*k;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[n - 1][2*k];
        }
    }

**一维**(参考)

class Solution {
        
        public int maxProfit(int k, int[] prices) {
        
            if(prices.length == 0){
        
                return 0;
            }
            if(k == 0){
        
                return 0;
            }
            // 其实就是123题的扩展，123题只用记录2次交易的状态
            // 这里记录k次交易的状态就行了
            // 每次交易都有买入，卖出两个状态，所以要乘 2
            int[] dp = new int[2 * k];
            // 按123题解题格式那样，做一个初始化
            for(int i = 0; i < dp.length / 2; i++){
        
                dp[i * 2] = -prices[0];
            }
            for(int i = 1; i <= prices.length; i++){
        
                dp[0] = Math.max(dp[0], -prices[i - 1]);
                dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);
                // 还是与123题一样，与123题对照来看
                // 就很容易啦
                for(int j = 2; j < dp.length; j += 2){
        
                    dp[j] = Math.max(dp[j], dp[j - 1] - prices[i-1]);
                    dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i - 1]);
                }
            }
            // 返回最后一次交易卖出状态的结果就行了
            return dp[dp.length - 1];
        }
    }

#### 25、最佳买卖股票时机含冷冻期 ####

[力扣题目链接][Link 5]

**动规五部曲**

*  **确定dp数组以及下标的含义**

`dp[i][j]`，第i天状态为j，所剩的最多现金为`dp[i][j]`。

*  **确定递推公式**
 *  状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）`dp[i][0]`
 *  卖出股票状态，这里就有两种卖出股票状态
    
     *  状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态`dp[i][1]`
     *  状态三：今天卖出了股票`dp[i][2]`
 *  状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！`dp[i][3]`

**达到买入股票状态（状态一）即：`dp[i`\]\[0\]，有两个具体操作：**

*  操作一：前一天就是持有股票状态（状态一），`dp[i][0] = dp[i - 1][0]`
 *  操作二：今天买入了，有两种情况
    
     *  前一天是冷冻期（状态四），`dp[i - 1][3] - prices[i]`
     *  前一天是保持卖出股票状态（状态二），`dp[i - 1][1] - prices[i]`

所以操作二取最大值，即：`max(dp[i - 1][3], dp[i - 1][1]) - prices[i]`

那么`dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);`

达到保持卖出股票状态（状态二）即：`dp[i][1]`，有两个具体操作：

*  操作一：前一天就是状态二
 *  操作二：前一天是冷冻期（状态四）

`dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])`;

达到今天就卖出股票状态（状态三），即：`dp[i][2]` ，只有一个操作：

*  操作一：昨天一定是买入股票状态（状态一），今天卖出

即：`dp[i][2] = dp[i - 1][0] + prices[i]`;

达到冷冻期状态（状态四），即：`dp[i][3]`，只有一个操作：

*  操作一：昨天卖出了股票（状态三）

`dp[i][3] = dp[i - 1`\]\[2\];

综上分析，递推代码如下：

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

*  **dp数组初始化**

对于在定义中没有意义的数组，可通过递推公式确定

dp[0][0] = -prices[0];
    dp[0][1] = 0;
    dp[0][2] = 0;
    dp[0][3] = 0;

*  **确定遍历顺序**

从递归公式上可以看出，`dp[i] 依赖于 dp[i-1]`，所以是从前向后遍历。

*  **举例并推导dp数组**

![image-20221217111152412][]

**取最大值**

return Math.max(dp[n-1][1],Math.max(dp[n-1][2],dp[n-1][3]));

**Code**

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if(prices==null|prices.length==0) return 0;
            int n = prices.length;
            int[][] dp = new int[n][4];
            dp[0][0] = -prices[0];
            dp[0][1] = 0;
            dp[0][2] = 0;
            dp[0][3] = 0;
            for(int i = 1;i < n;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[n-1][1],Math.max(dp[n-1][2],dp[n-1][3]));
        }
    }

#### 26、买卖股票的最佳时机含手续费 ####

[力扣题目链接][Link 6]

**动规五部曲**

*  **确定dp数组以及下标的含义**

\`\`dp\[i\]\[j\]\`表示第i天的状态为j，所剩的最多现金

*  **确定递推公式**

`dp[i][0]` 表示第i天持有股票所剩最多现金。 `dp[i][1]` 表示第i天不持有股票所得最多现金

如果第i天持有股票即`dp[i][0]`， 那么可以由两个状态推出来

*  第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：`dp[i - 1][0]`
 *  第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：`dp[i - 1][1] - prices[i]`

在来看看如果第i天不持有股票即`dp[i][1]`的情况， 依然可以由两个状态推出来

*  第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：`dp[i - 1][1]`
 *  第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：`dp[i - 1][0] + prices[i] - fee`

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

*  **dp数组初始化**

dp[0][0] = -prices[0];
            dp[0][1] = 0;

*  **确定遍历顺序**

从递归公式上可以看出，`dp[i] 依赖于 dp[i-1]`，所以是从前向后遍历。

**Code**

二维

class Solution {
        
        public int maxProfit(int[] prices, int fee) {
        
            if(prices==null||prices.length==0) return 0;
            int n = prices.length;
            int[][] dp = new int[n][2];
            dp[0][0] = -prices[0];
            dp[0][1] = 0;
            for(int i = 1;i < n;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[n-1][1];
        }
    }

一维

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

### 股票问题总结篇 ###

![image-20221217115042848][]

**卖股票的最佳时机**

【动态规划】

*  `dp[i][0]` 表示第i天持有股票所得现金。
 *  `dp[i][1]` 表示第i天不持有股票所得现金。

如果第i天持有股票即`dp[i][0]`， 那么可以由两个状态推出来

*  第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：`dp[i - 1][0]`
 *  第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices\[i\] 所以`dp[i][0] = max(dp[i - 1][0], -prices[i]);`

如果第i天不持有股票即`dp[i][1]`， 也可以由两个状态推出来

*  第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：`dp[i - 1][1]`
 *  第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：`prices[i] + dp[i - 1][0] 所以dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);`

**Code**

**买卖股票的最佳时机II**

【动态规划】

dp数组定义：

*  `dp[i][0]` 表示第i天持有股票所得现金
 *  `dp[i][1]` 表示第i天不持有股票所得最多现金

如果第i天持有股票即`dp[i][0]`， 那么可以由两个状态推出来

在[121. 买卖股票的最佳时机][121.]中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即`dp[i][0]`一定就是 -prices\[i\]。

而本题\*\*，因为一只股票可以买卖多次\*\*，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。

**Code**

**二维数组**

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if(prices==null||prices.length==0){
        
                return 0;
            }
            int n = prices.length;
            int[][] dp = new int[n][2];
            dp[0][1] = -prices[0];
            dp[0][0] = 0;
            for(int i = 1; i < n; 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];
        }
    }

**一维数组**

**买卖股票的最佳时机Ⅲ**

【动态规划】

一天一共就有五个状态，

1.  没有操作
2.  第一次买入
3.  第一次卖出
4.  第二次买入
5.  第二次卖出

`dp[i][j]`中 i表示第i天，j为 \[0 - 4\] 五个状态，`dp[i][j]`表示第i天状态j所剩最大现金。

达到`dp[i][1]`状态，有两个具体操作：

*  操作一：第i天买入股票了，那么`dp[i][1] = dp[i-1][0] - prices[i]`
 *  操作二：第i天没有操作，而是沿用前一天买入的状态，即：`dp[i][1] = dp[i - 1][1]`

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

同理`dp[i][2]`也有两个操作：

*  操作一：第i天卖出股票了，那么`dp[i][2] = dp[i - 1][1] + prices[i]`
 *  操作二：第i天没有操作，沿用前一天卖出股票的状态，即：`dp[i][2] = dp[i - 1][2]`

所以`dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])`

同理可推出剩下状态部分：

`dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);`

`dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);`

**Code**

**二维**

**一维**

**买卖股票的最佳时机Ⅳ**

使用二维数组 `dp[i][j]` ：第i天的状态为j，所剩下的最大现金是`dp[i][j]`

j的状态表示为：

*  0 表示不操作
 *  1 第一次买入
 *  2 第一次卖出
 *  3 第二次买入
 *  4 第二次卖出
 *  …

**除了0以外，偶数就是卖出，奇数就是买入**。

1.  确定递推公式

达到`dp[i][1]`状态，有两个具体操作：

*  操作一：第i天买入股票了，那么`dp[i][1] = dp[i - 1][0] - prices[i]`
 *  操作二：第i天没有操作，而是沿用前一天买入的状态，即：`dp[i][1] = dp[i - 1][1]`

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

同理`dp[i][2]`也有两个操作：

*  操作一：第i天卖出股票了，那么`dp[i][2] = dp[i - 1][1] + prices[i]`
 *  操作二：第i天没有操作，沿用前一天卖出股票的状态，即：`dp[i][2] = dp[i - 1][2]`

`dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])`

**Code**

**二维**：股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作

**一维**(参考)

**最佳买卖股票时机含冷冻期**

*  `dp[i][j]`，第i天状态为j，所剩的最多现金为`dp[i][j]`。
 *  状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）`dp[i][0]`
 *  卖出股票状态，这里就有两种卖出股票状态
    
     *  状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态`dp[i][1]`
     *  状态三：今天卖出了股票`dp[i][2]`
 *  状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！`dp[i][3]`

**达到买入股票状态（状态一）即：`dp[i`\]\[0\]，有两个具体操作：**

所以操作二取最大值，即：`max(dp[i - 1][3], dp[i - 1][1]) - prices[i]`

那么`dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);`

达到保持卖出股票状态（状态二）即：`dp[i][1]`，有两个具体操作：

*  操作一：前一天就是状态二
 *  操作二：前一天是冷冻期（状态四）

`dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])`;

达到今天就卖出股票状态（状态三），即：`dp[i][2]` ，只有一个操作：

*  操作一：昨天一定是买入股票状态（状态一），今天卖出

即：`dp[i][2] = dp[i - 1][0] + prices[i]`;

达到冷冻期状态（状态四），即：`dp[i][3]`，只有一个操作：

*  操作一：昨天卖出了股票（状态三）

`dp[i][3] = dp[i - 1`\]\[2\];

综上分析，递推代码如下：

**Code**

**买卖股票的最佳时机含手续费**

*  `dp[i][j]`表示第i天的状态为j，所剩的最多现金
 *  `dp[i][0]` 表示第i天持有股票所剩最多现金。 `dp[i][1]` 表示第i天不持有股票所得最多现金,如果第i天持有股票即`dp[i][0]`， 那么可以由两个状态推出来
 *  第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：`dp[i - 1][0]`
 *  第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：`dp[i - 1][1] - prices[i]`

在来看看如果第i天不持有股票即`dp[i][1]`的情况， 依然可以由两个状态推出来

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

**Code**

二维

一维

####  ####

[Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
[Link 2]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
[Link 3]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
[image-20221212220237134]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/871a21bb52d841d6909d8a20b695b9ee.png
[Link 4]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
[image-20221214195453126]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d76914339e544c1cb80af222f32e085c.png
[Link 5]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[image-20221217111152412]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/44c5670e744d4f65aaecf4f8743beb89.png
[Link 6]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[image-20221217115042848]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f7370281541845ef89d2231ab5c7560e.png
[121.]: https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html