【算法优选】动态规划之简单多状态dp问题——贰

比眉伴天荒 2024-04-17 10:55 64阅读 0赞

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

*  ?前言
 *  ?\[买卖股票的最佳时机含冷冻期\](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/)
 *   *  ?题目描述
     *  ?算法思路：
     *   *  ?状态表示：
         *  ?状态转移方程：
         *  ?初始化：
         *  ?填表顺序：
         *  ?返回值：
     *  ?代码实现
 *  ?\[买卖股票的最佳时期含手续费（medium）\](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/)
 *   *  ?题目描述
     *  ?算法思路
     *   *  ?状态表示：
         *  ?状态转移方程：
         *  ?初始化：
         *  ?填表顺序：
         *  ?返回值：
     *  ?代码实现
 *  ?\[买卖股票的最佳时机 III\](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/)
 *   *  ?题目描述
     *  ?算法思路
     *   *  ?状态表示：
         *  ?状态转移方程：
         *  ?初始化：
         *  ?填表顺序：
         *  ?返回值：
     *  ?代码实现
 *  ⭕总结

## ?前言 ##

动态规划相关题目都可以参考以下五个步骤进行解答：

1.  状态表示
2.  状态转移⽅程
3.  初始化
4.  填表顺序
5.  返回值

后面题的解答思路也将按照这五个步骤进行讲解。

## ?[买卖股票的最佳时机含冷冻期][Link 1] ##

### ?题目描述 ###

给定一个整数数组prices，其中第 prices\[i\] 表示第 i 天的股票价格

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

*  示例 1:  
    输入: prices = \[1,2,3,0,2\]  
    输出: 3  
    解释: 对应的交易状态为: \[买入, 卖出, 冷冻期, 买入, 卖出\]
 *  示例 2:  
    输入: prices = \[1\]  
    输出: 0

class Solution {
        
        public int maxProfit(int[] prices) {
        
    
        }
    }

### ?算法思路： ###

#### ?状态表示： ####

对于线性dp ，我们可以⽤「经验+题⽬要求」来定义状态表示：

*  以某个位置为结尾…；
 *  以某个位置为起点…。

这里我们选择比较常⽤的⽅式，以某个位置为结尾，结合题目要求，定义⼀个状态表⽰：

由于有「买⼊」「可交易」「冷冻期」三个状态，因此我们可以选择⽤三个数组，其中：

*  dp\[i\]\[0\] 表⽰：第 i 天结束后，处于「买⼊」状态，此时的最⼤利润；
 *  dp\[i\]\[1\]表⽰：第 i 天结束后，处于「可交易」状态，此时的最⼤利润；
 *  dp\[i\]\[2\] 表⽰：第 i 天结束后，处于「冷冻期」状态，此时的最⼤利润。

#### ?状态转移方程： ####

我们要谨记规则：

1.  处于「买⼊」状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖出股票；
2.  处于「卖出」状态的时候：
    
     *  如果「在冷冻期」，不能买⼊；
     *  如果「不在冷冻期」，才能买⼊。

对于 dp\[i\]\[0\] ，我们有「两种情况」能到达这个状态：

1.  在 i - 1 天持有股票，此时最⼤收益应该和 i - 1 天的保持⼀致： dp\[i - 1\]\[0\] ；
2.  在 i 天买⼊股票，那我们应该选择 i - 1 天不在冷冻期的时候买⼊，由于买⼊需要花钱，所以此时最⼤收益为： dp\[i - 1\]\[1\] - prices\[i\]

两种情况应取最⼤值，因此： dp\[i\]\[0\] = max(dp\[i - 1\]\[0\], dp\[i - 1\]\[1\] - prices\[i\]) 。

对于 dp\[i\]\[1\] ，我们有「两种情况」能到达这个状态：

1.  在 i - 1 天的时候，已经处于冷冻期，然后啥也不⼲到第 i 天，此时对应的状态为：dp\[i - 1\]\[2\] ；
2.  在 i - 1 天的时候，⼿上没有股票，也不在冷冻期，但是依旧啥也不干到第 i 天，此时对应的状态为 dp\[i - 1\]\[1\] ；

两种情况应取最⼤值，因此： dp\[i\]\[1\] = max(dp\[i - 1\]\[1\], dp\[i - 1\]\[2\]) 。

对于 dp\[1\]\[i\] ，我们只有「⼀种情况」能到达这个状态：

1.  在 i - 1 天的时候，卖出股票。
2.  因此对应的状态转移为： dp\[i\]\[2\] = dp\[i - 1\]\[0\] + prices\[i\]

#### ?初始化： ####

三种状态都会用到前⼀个位置的值，因此需要初始化每⼀行的第⼀个位置：

*  dp\[0\]\[0\] ：此时要想处于「买⼊」状态，必须把第⼀天的股票买了，因此 dp\[0\]\[0\] = -prices\[0\] ；
 *  dp\[0\]\[1\] ：啥也不用干即可，因此 dp\[0\]\[1\] = 0 ；
 *  dp\[0\]\[2\] ：⼿上没有股票，买⼀下卖⼀下就处于冷冻期，此时收益为 0 ，因此 dp\[0\]\[2\]= 0 。

#### ?填表顺序： ####

根据「状态表示」，我们要三个表⼀起填，每⼀个表「从左往右」。

#### ?返回值： ####

应该返回「卖出状态」下的最⼤值，因此应该返回 max(dp\[n - 1\]\[1\], dp\[n - 1\]\[2\])

### ?代码实现 ###

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

## ?[买卖股票的最佳时期含手续费（medium）][medium] ##

### ?题目描述 ###

给定一个整数数组 prices，其中 prices\[i\]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

*  示例 1：  
    输入：prices = \[1, 3, 2, 8, 4, 9\], fee = 2  
    输出：8  
    解释：能够达到的最大利润:  
    在此处买入 prices\[0\] = 1  
    在此处卖出 prices\[3\] = 8  
    在此处买入 prices\[4\] = 4  
    在此处卖出 prices\[5\] = 9  
    总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
 *  示例 2：  
    输入：prices = \[1,3,7,5,10,3\], fee = 3  
    输出：6

class Solution {
        
        public int maxProfit(int[] prices, int fee) {
        
    
        }
    }

### ?算法思路 ###

#### ?状态表示： ####

对于线性 dp ，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：

1.  以某个位置为结尾，进行操作；
2.  以某个位置为起点，进行操作。

这里我们选择比较常用的方式，以某个位置为结尾，结合题目要求，定义⼀个状态表示：

由于有「买⼊」「可交易」两个状态，因此我们可以选择用两个数组，其中：

*  f\[i\] 表示：第 i 天结束后，处于「买⼊」状态，此时的最大利润；
 *  g\[i\] 表示：第 i 天结束后，处于「卖出」状态，此时的最大利润。

#### ?状态转移方程： ####

我们选择在「卖出」的时候，支付这个手续费，那么在「买入」的时候，就不⽤再考虑⼿续费的问题。

对于 f\[i\] ，我们有两种情况能到达这个状态：

1.  在 i - 1 天「持有」股票，第 i 天啥也不干。此时最⼤收益为 f\[i - 1\] ；
2.  在 i - 1 天的时候「没有」股票，在第 i 天买⼊股票。此时最⼤收益为 g\[i - 1\] - prices\[i\])

两种情况下应该取最大值，因此 f\[i\] = max(f\[i - 1\], g\[i - 1\] -prices\[i\]) 。

对于 g\[i\] ，我们也有两种情况能够到达这个状态：

1.  在 i - 1 天「持有」股票，但是在第 i 天将股票卖出。此时最大收益为： f\[i - 1\]+ prices\[i\] - fee) ，记得手续费；
2.  在 i - 1 天「没有」股票，然后第 i 天啥也不干。此时最大收益为： g\[i - 1\] ；

两种情况下应该取最大值，因此 g\[i\] = max(g\[i - 1\], f\[i - 1\] + prices\[i\] - free) 。

class Solution {
        
        public int maxProfit(int[] prices, int fee) {
        
            int[] f = new int[prices.length];
            int[] g = new int[prices.length];
            f[0] = -prices[0];
            for (int i = 1; i < prices.length; i++) {
        
                f[i] = Math.max(f[i - 1],g[i - 1] - prices[i]);
                g[i] = Math.max(g[i - 1], f[i - 1] + prices[i] - fee); 
            }
            return g[prices.length - 1];
        }
    }

#### ?初始化： ####

由于需要用到前面的状态，因此需要初始化第⼀个位置。

*  对于 f\[0\] ，此时处于「买入」状态，因此 f\[0\] = -prices\[0\] ；
 *  对于 g\[0\] ，此时处于「没有股票」状态，啥也不干即可获得最大收益，因此 g\[0\] = 0

#### ?填表顺序： ####

毫⽆疑问是「从左往右」，但是两个表需要⼀起填。

#### ?返回值： ####

应该返回「卖出」状态下，最后⼀天的最大值收益： g\[n - 1\]

### ?代码实现 ###

## ?[买卖股票的最佳时机 III][III] ##

### ?题目描述 ###

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

*  示例 1:  
    输入：prices = \[3,3,5,0,0,3,1,4\]  
    输出：6  
    解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。  
    随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。  
    \-示例 2：  
    输入：prices = \[1,2,3,4,5\]  
    输出：4  
    解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
    注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
    因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
 *  示例 3：  
    输入：prices = \[7,6,4,3,1\]  
    输出：0  
    解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
 *  示例 4：  
    输入：prices = \[1\]  
    输出：0

class Solution {
        
        public int maxProfit(int[] prices) {
        
    
        }
    }

### ?算法思路 ###

#### ?状态表示： ####

对于线性 dp ，我们可以⽤「经验 + 题目要求」来定义状态表示：

1.  以某个位置为结尾，进行一系列操作；
2.  以某个位置为起点，进行一系列操作。

这里我们选择比较常⽤的⽅式，以某个位置为结尾，结合题目要求，定义⼀个状态表⽰：

由于有「买⼊」「可交易」两个状态，因此我们可以选择用两个数组。但是这道题⾥⾯还有交易次数的限制，因此我们还需要再加上⼀维，用来表示交易次数。其中：

*  f\[i\]\[j\] 表⽰：第 i 天结束后，完成了 j 次交易，处于「买⼊」状态，此时的最⼤利润；
 *  g\[i\]\[j\] 表⽰：第 i 天结束后，完成了 j 次交易，处于「卖出」状态，此时的最⼤利润。

#### ?状态转移方程： ####

对于 f\[i\]\[j\] ，我们有两种情况到这个状态：

1.  在 i - 1 天的时候，交易了 j 次，处于「买⼊」状态，第 i 天啥也不干即可。此时最大利润为： f\[i - 1\]\[j\] ；
2.  在 i - 1 天的时候，交易了 j 次，处于「卖出」状态，第 i 天的时候把股票买了。此时的最⼤利润为： g\[i - 1\]\[j\] - prices\[i\] 。

综上，我们要的是「最⼤利润」，因此是两者的最⼤值： f\[i\]\[j\] = max(f\[i - 1\]\[j\],g\[i - 1\]\[j\] - prices\[i\]) 。

对于 g\[i\]\[j\] ，我们也有两种情况可以到达这个状态：

1.  在 i - 1 天的时候，交易了 j 次，处于「卖出」状态，第 i 天啥也不⼲即可。此时的最大利润为： g\[i - 1\]\[j\] ；
2.  在 i - 1 天的时候，交易了 j - 1 次，处于「买⼊」状态，第 i 天把股票卖了，然后就完成了 j ⽐交易。此时的最⼤利润为： f\[i - 1\]\[j - 1\] + prices\[i\] 。但是这个状态不⼀定存在，要先判断⼀下。

综上，我们要的是最⼤利润，因此状态转移方程为：

g[i][j] = g[i - 1][j];
    if(j >= 1) {
        
    	g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
    }

#### ?初始化： ####

由于需要用到 i = 0 时的状态，因此我们初始化第⼀行即可。

*  当处于第 0 天的时候，只能处于「买⼊过⼀次」的状态，此时的收益为 -prices\[0\] ，因此 f\[0\]\[0\] = - prices\[0\] 。
 *  为了取 max 的时候，⼀些不存在的状态「起不到干扰」的作用，我们统统将它们初始化为 - INF （用 INT\_MIN 在计算过程中会有「溢出」的风险，这⾥ INF 折半取0x3f3f3f3f ，足够小即可）

#### ?填表顺序： ####

从「上往下填」每⼀行，每⼀行「从左往右」，两个表「⼀起填」。

#### ?返回值： ####

返回处于「卖出状态」的最⼤值，但是我们也「不知道是交易了⼏次」，因此返回 g 表最后⼀行的最大值。

### ?代码实现 ###

class Solution {
        
        public int maxProfit(int[] prices) {
        
            // 1. 创建 dp 表
            // 2. 初始化
            // 3. 填表
            // 4. 返回值
            int INF = 0x3f3f3f3f;
            int n = prices.length;
            int[][] f = new int[n][3];
            int[][] g = new int[n][3];
            for(int j = 0; j < 3; j++) {
        
                f[0][j] = g[0][j] = -INF;
            }
            f[0][0] = -prices[0];
            g[0][0] = 0;
            for(int i = 1; i < n; i++) {
        
                for (int j = 0; j < 3; j++) {
        
                    f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                    g[i][j] = g[i - 1][j];
                    // 判断状态是否存在
                    if (j - 1 >= 0) {
        
                        g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                    }
                }
            }
            //找出最后一行的最大值
            int ret = 0; 
            for(int j = 0; j < 3; j++) {
        
                ret = Math.max(ret, g[n - 1][j]);
            }
            return ret;
        }
    }

## ⭕总结 ##

关于《【算法优选】 动态规划之简单多状态dp问题——贰》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
[medium]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
[III]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/