目录

引入：

例题1：按摩师（打家劫舍I）

例题2：打家劫舍II

例题3：删除并获得点数

例题4：粉刷房子

例题5：买卖股票的最佳时机含冷冻

结语：

---

引入：

相信看到这里的友友们对动态规划已经有了一定的了解，下面我将介绍动态规划的简单多状态dp问题。所谓多状态就是在一步下有不同的情况要区分（例如买股票，今天可以分为买还是不买的多两种情况）。由于算法只讲知识点是远远不够的故下面我会在例题中穿插知识点帮助理解。动态规划一般的解题步骤还是1. 状态表示，2.状态转移方程，3.初始化，4.填表顺序，5.返回值。在写代码时一定要把这5步考虑清楚再写代码。

例题1：按摩师（打家劫舍I）

链接：按摩师

题目简介：

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

解法（动态规划）：

1. 状态表示：

对于简单的线性dp ，我们可以用「经验+题⽬要求」来定义状态表示例如：

（1）以某个位置为结尾的最小花费。

（2）以某个位置为起点到终点的最小花费。

故我们这题采用常用的方式：dp[i] 表⽰：选择到i 位置时，此时的最⻓预约时⻓。由于我们这个题在i 位置的时候，会⾯临选择或者不选择两种抉择，所依赖的状态需要细分。

下面之所以用f和g是因为高中我们所学的f（x）和g（x），可以换成其他的（但最好用f和g就当作是不成文的规定，这样代码的可读性会更高）。

（1）f[i] 表示：选择到i 位置时， nums[i] 必选，此时的最⻓预约时⻓。

（2）g[i]表示：选择到i 位置时， nums[i] 不选，此时的最⻓预约时⻓。

2.状态转移方程

因为状态表示定义了两个，因此我们的状态转移⽅程也要分析两个：

对于f[i] ：

如果nums[i] 必选，那么我们仅需知道i - 1 位置在不选的情况下的最⻓预约时⻓， 然后加上nums[i] 即可，因此f[i] = g[i - 1] + nums[i] 。

对于g[i] ：

如果nums[i] 不选，那么i - 1 位置上选或者不选都可以。因此，我们需要知道i - 1 位置上选或者不选两种情况下的最⻓时⻓，因此g[i] = max(f[i - 1], g[i - 1]) 。

在状态转移方程这里可以画图来帮助我们理解

3.初始化

这道题的初始化⽐较简单，因此⽆需加辅助节点（前两篇文章已解释），仅需初始化f[0] = nums[0], g[0] = 0 即可。

4.填表顺序

根据「状态转移⽅程」得「从左往右，两个表⼀起填」。

5.返回值

根据「状态表示」，应该返回max(f[n - 1], g[n - 1]) 。

代码实现如下：

class Solution {
    public int massage(int[] nums) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        int[] f = new int[n];//选择
        int[] g = new int[n];//不选择
        f[0] = nums[0];
        for(int i = 1;i < n;i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(g[i - 1],f[i - 1]);
        }
        return Math.max(g[n -1],f[n - 1]);
    }
}

时间复杂度：O（n）

空间复杂度：O（n）

例题2：打家劫舍II

链接：打家劫舍II

题目简介：

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

 解法（动态规划）：

通过阅读题目友友可以发现这题和例题一是差不多的，唯一不同就是例题二加了一个末尾和开头的限制。上⼀个问题是⼀个「单排」的模式，这⼀个问题是⼀个「环形」的模式，也就是⾸尾是相连的。但是我们可以将「环形」问题转化为「两个单排」问题：

（1）偷第⼀个房屋时的最大⾦额x ，此时不能偷最后⼀个房⼦，因此就是偷[0, n - 2] 区间的房⼦。

（2）不偷第⼀个房屋时的最大⾦额y ，此时可以偷最后⼀个房⼦，因此就是偷[1, n - 1] 区 间的房⼦。

两种情况下的「最大值」，就是最终的结果。

代码如下：

下面的rob1方法就是例题一。

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + rob1(nums,2,n - 2), rob1(nums,1,n - 1));
    }
    public int rob1(int[] nums,int left,int right){
        if(left > right){
            return 0;
        }
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left] = nums[left];
        for(int i = left + 1;i <= right;i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(g[i - 1],f[i - 1]);
        }
        return Math.max(f[right],g[right]);
    }
}

时间复杂度：O（n） 

空间复杂度：O（n）

例题3：删除并获得点数

链接：删除并获得点数

题目简介：

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

解法（动态规划）：

其实这道题依旧是「打家劫舍I」问题的变型。 我们注意到题⽬描述，选择x 数字的时候， x - 1 与x + 1 是不能被选择的。像不像「打家劫舍」问题中，选择i 位置的⾦额之后，就不能选择i - 1 位置(数组中)以及i + 1 位置的⾦额呢~ 因此，我们可以创建⼀个⼤⼩为10001 （根据题⽬的数据范围）的hash 数组，将nums 数 组中每⼀个元素x ，累加到hash 数组下标为x 的位置处，然后在hash数组上来⼀次「打家劫舍」即可。

过程如下图：

弧线表示0到i - 1之间能获得的最大点数。

代码如下：

class Solution {
    public int deleteAndEarn(int[] nums) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int n = 10001;
        int[] arr = new int[n];
        for(int x:nums){
            arr[x] += x;
        }
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = arr[0];
        for(int i = 1;i < n;i++){
            f[i] = g[i - 1] + arr[i];
            g[i] = Math.max(f[i - 1],g[i - 1]);
        }
        return Math.max(f[n - 1],g[n - 1]);
    }
}

时间复杂度：O（n） 

空间复杂度：O（n）

例题4：粉刷房子

链接：粉刷房⼦

题目简介：

 解法（动态规划）：

 1. 状态表示：

对于线性dp ，我们可以⽤「经验+题⽬要求」来定义状态表⽰：但是我们这个题在i 位置的时候，会⾯临「红」「蓝」「绿」三种抉择，所依赖的状态需要细分：

（1）dp[i][0] 表⽰：粉刷到i 位置的时候，最后⼀个位置粉刷上「红⾊」，此时的最⼩花费。 

（2）dp[i][1] 表⽰：粉刷到i 位置的时候，最后⼀个位置粉刷上「蓝⾊」，此时的最⼩花费。

（3）dp[i][2] 表⽰：粉刷到i 位置的时候，最后⼀个位置粉刷上「绿⾊」，此时的最⼩花费。

 2.状态转移方程

因为状态表⽰定义了三个，因此我们的状态转移⽅程也要分析三个：

对于dp[i][0] ：

如果第i个位置粉刷上「红⾊」，那么i-1位置上可以是「蓝⾊」或者「绿⾊」。因此我们 需要知道粉刷到i-1位置上的时候，粉刷上「蓝⾊」或者「绿⾊」的最⼩花费，然后加上i 位置的花费即可。于是状态转移⽅程为： dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0] ;

同理，我们可以推导出另外两个状态转移⽅程为：

dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1] ；

dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2] 。

 3.初始化

采用最前⾯加上⼀个「辅助结点」。

注意点：(1)辅助结点⾥⾯的值要「保证后续填表是正确的」(2)「下标的映射关系」。

 4.填表顺序

 5.返回值

根据「状态表⽰」，应该返回最后⼀个位置粉刷上三种颜⾊情况下的最⼩值，因此需要返回： min(dp[n][0], min(dp[n][1], dp[n][2])) 。

代码如下：

class Solution {
    public int minCost(int[][] costs) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int n = costs.length;
        int[][] dp = new int[n + 1][3];
        for(int i = 1;i <= n;i++){
            dp[i][0] = Math.min(dp[i - 1][1],dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = Math.min(dp[i - 1][0],dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = Math.min(dp[i - 1][1],dp[i - 1][0]) + costs[i - 1][2];
        }
        return Math.min(dp[n][0],Math.min(dp[n][1],dp[n][2]));
    }
}

时间复杂度：O（n） 

空间复杂度：O（n）

例题5：买卖股票的最佳时机含冷冻

链接：买卖股票的最佳时机含冷冻期

题目简介：

  解法（动态规划）：

 1. 状态表示：

这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：由于有「买⼊」「可交易」「冷冻期」三个状态，因此我们可以选择⽤三个数组，其中：

（1）dp[i][0] 表⽰：第i 天结束后，处于「买⼊」状态，此时的最⼤利润。

（2）dp[i][1] 表⽰：第i 天结束后，处于「可交易」状态，此时的最⼤利润。

（3）dp[i][2] 表⽰：第i 天结束后，处于「冷冻期」状态，此时的最⼤利润。

我们要谨记规则：

（1）处于「买⼊」状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖 出股票；

（2）处于「买⼊」状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖 出股票；

 2.状态转移方程

确定状态表示后，我们可以画图来帮助我们理解根据题目要求我们可以画图下图，并推出状态转移方程。

 3.初始化

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

dp[0][0] ：此时要想处于「买⼊」状态，必须把第⼀天的股票买了，因此dp[0][0] = - prices[0] ； dp[0][1] ：啥也不⽤⼲即可，因此dp[0][1] = 0 ；

dp[0][2] ：手上没有股票，买⼀下卖⼀下就处于冷冻期，此时收益为0 ，因此 dp[0][2] = 0 。

4.填表顺序

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

5.返回值

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

代码如下：

class Solution {
    public int maxProfit(int[] prices) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        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]);
    }
}

时间复杂度：O（n） 

空间复杂度：O（n）

结语：

其实写博客不仅仅是为了教大家，同时这也有利于我巩固自己的知识点，和一个学习的总结，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进，如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。