【动态规划】简单多状态dp问题（1）打家劫舍问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划】简单多状态dp问题（1）打家劫舍问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

打家劫舍问题

【动态规划】简单多状态dp问题（1）打家劫舍问题

1. 按摩师（打家劫舍Ⅰ）

传送门：面试题 17.16. 按摩师

题目：

1.1 题目解析

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

越难的dp问题，看示例只能起到了解题目的效果，一般推不出啥普遍的规律，所以接下来就是我们的算法原理，通过动归的思想去理解，才会豁然开朗！

1.2 算法原理

1.2.1 状态表示

我们需要通过经验 + 题目要求去决定状态表示：

根据题目的意境以及数据结构，我们得出需要建立一维的dp表（大小为 n）
- 对于为什么用一维，首先这道题数据结构为一维的，而一维如果确实可以解决问题就没有必要上升到二维
经验：以某个坐标为结尾或者以某个坐标为起点去研究题目问题！
- 此题用的是“结尾”

再根据经验，一般dp表的其中一值就应该是答案！

所以含义应该就是“最长预约时长”

综合得到状态表示：dp[i]表示就是起点到坐标为 i 的位置这些天以来的最长预约时长

而这道题，与之前做过的题不一样的是，一个坐标的状态有两种情况，需要我们继续细化

接单
不接单

在之前的题目里，我们到达一个坐标并无其他选择，而现在有~

而我们需要有两个dp表来细化表示这两个状态，因为一个dp表是无法表示这两种状态的，这就是简单的多状态dp问题的关键！

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

其中 f 和 g 对应中学阶段的函数 f 和函数 g 的这种常用的写法
当然也可以写成二维数组（n × 2）

所以，最终的状态表示为：

f[i]表示的是，从起点到 i 坐标的这些天内，i这一天接单的情况下的最长预约时间

g[i]表示的是，从起点到 i 坐标的这些天内，i这一天不接单的情况下的最长预约时间

1.2.2 状态转移方程

同样的套路，我们需要根据已确定的dp表的值来推导 f[i] 和 g[i] 的值，并且牢记他们的状态表示！

我们以坐标 i 为结尾
根据“最近一步”去划分问题

“最近一步”可以理解为“必然事件”

此题的“必然事件”就是，到达坐标 i 之前，必然要先到达坐标 i - 1

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

这一天如果接单的话，那么前一天就必须不接单，那么预约时长为今天的预约时长nums[i]加上，上一天的不接单情况下的最长预约时长g[i - 1]
这一天如果不接单的话，那么前一天可以接单，也可以不接单，那么预约时长则是，前一天接单情况和不接单情况的最长预约时长中的较大值

而1代表着f表怎么填，2代表着g表怎么填

所以得出状态转移方程：

f[i] = nums[i] + g[i - 1];

g[i] = max{f[i - 1], g[i - 1]};

1.2.3 初始化

这道题可以用假数据的方法，但是没有必要，因为我们只需要初始化第一个值就行了~

如果第一天接单，则预约时长就是nums[0]
如果第一天不接单，则预约时长就是0

1.2.4 填表顺序

从左往右两个表一起填

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

1.2.5 返回值

返回的就是起点到终点，即所有天以来的最长预约时长，即f[n - 1]或者g[n - 1]

最后一天两种可能都有，所以返回其较大值！

1.3 编写代码

根据算法原理编写代码即可：

创建dp表
初始化，处理边界问题
填表
返回值

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] = nums[i] + g[i - 1];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[n - 1], g[n - 1]);  
    }
}

时空复杂度都为：O(N)

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

2. 打家劫舍Ⅱ

传送门：力扣213. 打家劫舍 II

题目：

2.1 题目解析

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

2.2 算法原理

算法原理基本跟上一道题一致，只不过这一次成环了~

而并不想在状态转移方程中去判断这种情况，因为这是不现实的，因为f 表和g 表到达n - 2下标的时候，我们并不能确定n - 2坐标对应的情况，起点是否“偷”与“不偷”，并且我们也不能人为规定（影响最终结果）

而我们也不能以环型的形式去创建dp表！

所以我们需要一个**预处理**的阶段：（往已知的解法靠拢，化未知为已知）

我们细化第一天的状态：(重点理解)

偷，则次日和最后一天不能偷，相当于对[2, n - 2]进行一次打家劫舍，最终结果加上nums[0]
不偷，则最后一天无所谓，相当于对[1, n - 1]进行一次打家劫舍

而我们则需要去封装，“一次打家劫舍”的方法！

2.2.1 状态表示

我们需要通过经验 + 题目要求去决定状态表示：

根据题目的意境以及数据结构，我们得出需要建立一维的dp表（大小为不一定，由传入的范围决定）
- 本题有n-2大小，n-1大小
经验：以某个坐标为结尾或者以某个坐标为起点去研究题目问题！
- 此题用的是“结尾”

再根据经验，一般dp表的其中一值就应该是答案！

所以含义应该就是“最长预约时长”

综合得到状态表示：dp[i]表示就是起点到坐标为 i 的位置偷到的最大钱数

而这道题，与之前做过的题不一样的是，一个坐标的状态有两种情况，需要我们继续细化

偷
不偷

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

所以，最终的状态表示为：

f[i]表示的是，从起点到 i 坐标的这些房间，i这个房间偷的情况下的最大钱数

g[i]表示的是，从起点到 i 坐标的这些房间，i这个房间不偷的情况下的最大钱数

2.2.2 状态转移方程

同样的套路，我们需要根据已确定的dp表的值来推导 f[i] 和 g[i] 的值，并且牢记他们的状态表示！

我们以坐标 i 为结尾
根据“最近一步”去划分问题

“最近一步”可以理解为“必然事件”

此题的“必然事件”就是，到达坐标 i 之前，必然要先到达坐标 i - 1

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

这个房间如果偷的话，那么前一房间就必须不偷，那么金额为今天的钱额nums[i]加上，上一个房间的不偷情况下的最大金额g[i - 1]
这个房间如果不偷的话，那么前一个房间可以偷，也可以不偷，那么最大金额则是，前一个房间的偷情况和不偷情况的最大金额中的较大值

而1代表着f表怎么填，2代表着g表怎么填

所以得出状态转移方程：

f[i] = nums[i] + g[i - 1];

g[i] = max{f[i - 1], g[i - 1]};

2.2.3 初始化

本题由于要两次建表，而两次建表的填表起始点和终点都不一样
【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

第一个房间偷：
1. f[2] = nums[2]
2. g[2] = 0
第一个房间偷：
1. f[1] = nums[1]
2. g[2]

2.2.4 填表顺序

从左往右两个表一起填

第一个房间偷：从2开始填到n - 2
第二个房间偷：从1开始填到n - 1

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

2.2.5 返回值

第一个房间偷：最大值应该为f[n - 2]和g[n - 2]的较大值，再加上nums[0]
第一个房间偷：最大值应该为f[n - 1]和g[n - 2]的较大值

2.3 编写代码

一次打家劫舍操作的方法封装：

由于要与nums对应，所以我选择不限制dp表的大小，而是限制填表范围!

public int oneRob(int[] nums, int left, int right) {
    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] = nums[i] + g[i - 1];
        g[i] = Math.max(f[i - 1], g[i - 1]);
    }
    return Math.max(f[right], g[right]);
}

核心方法：

对于元素太少的边界情况要提前处理！

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) {
            return nums[0];
        }
        if(n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int yes = nums[0] + oneRob(nums, 2, n - 2);
        int no = oneRob(nums, 1, n - 1);
        return Math.max(yes, no);
    }
}

注意下标对应！

时空复杂度都为：O(N)
【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

3. 删除并获得点数

传送门：力扣740. 删除并获得点数

题目：

3.1 题目解析

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

3.2 算法原理

首先，我们需要将这些数据进行一个排序，这是很容易想到的，这样可以很好的观察到数据的发布情况（值为x的数的个数也明显）

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

而这样也不够，我们怎么往动态规划的方向去靠拢呢

现在还不能创建出dp表，因为如果按照nums的大小创建的话，那么下标对应的元素的状态也是不好确定的，例如：
1. 值相同的元素含义相同？
2. x-1和x-2不一定存在，且无法确认其下标

所以很快就能想到以下操作：

相同的元素“融合起来”
值与下标有关（哈希思想）：
- 顺手解决如何找到x-1和x+1的问题
对于不存在的值，默认对应值为0

猛地一看！

是不是就是打家劫舍问题！

问题：这样岂不是会选到不存在的数字？

对，但是没有关系，因为选择到不存在的数字，最终结果的情况中，不可能选择到不存在的数，因为这道题，nums元素都大于等于1，所以选择到不存在数字的时候，就相当于获得点数为0，反而导致我们不能选择一些高点数的东西
1. 相当于不选
2. 相当于自找苦头
所以在此情况下，选择不存在的数是自找苦吃的！
而如果nums元素的值没有正负限制，那么也没关系，因为选择这个不存在的数字，一样不会促进后续去获得点数，因为我们“不限制其选择不存在的数字”的情景下，他的最优解本来就可以不选那些大的负数即可，不需要靠选择不存在的数字来限制其不能选

即，不限制其选择不存在的数字，是完全考虑选择在不存在数字的情况下的强大的最优解

3.2.1 状态表示

我们需要通过经验 + 题目要求去决定状态表示：

根据题目的意境以及数据结构，我们得出需要建立一维的dp表（大小为输入案例nums数组的最大值 + 1，即**1e4 + 1**：科学计数法）
- 因为1e4也要对应到1e4下标
经验：以某个坐标为结尾或者以某个坐标为起点去研究题目问题！
- 此题用的是“结尾”

再根据经验，一般dp表的其中一值就应该是答案！

所以含义应该就是“最大点数”

综合得到状态表示：dp[i]表示就是起点到坐标为 i 的位置能获得的最大点数

而这道题，与之前做过的题不一样的是，一个坐标的状态有两种情况，需要我们继续细化

选
不选

所以，最终的状态表示为：

f[i]表示的是，从起点到 i 坐标的这些数内，i这一个数不选情况下能获得的最大点数

g[i]表示的是，从起点到 i 坐标的这些数内，i这一个数不选的情况下能获得的最大点数

3.2.2 状态转移方程

同样的套路，我们需要根据已确定的dp表的值来推导 f[i] 和 g[i] 的值，并且牢记他们的状态表示！

我们以坐标 i 为结尾
根据“最近一步”去划分问题

“最近一步”可以理解为“必然事件”

此题的“必然事件”就是，到达坐标 i 之前，必然要先到达坐标 i - 1

这个数如果选的话，那么x - 1就必须不选，那么获得点数为统计数组arr[i]加上，上一天的不选的情况下的能获得的最大点数g[i - 1]
这个数如果不选的话，那么前一天可以选，也可以不选，那么获得的点数则是，前一天选情况和不选情况的最大点数中的较大值

而1代表着f表怎么填，2代表着g表怎么填

所以得出状态转移方程：

f[i] = arr[i] + g[i - 1];

g[i] = max{f[i - 1], g[i - 1]};

3.2.3 初始化

0这个数是不存在的树，所以选和不选f[0]和g[0]都为0

3.2.4 填表顺序

从左往右两个表一起填

3.2.5 返回值

f[1e4] 和 g[1e4]的较大值

3.3 编写代码

预处理
创建dp表
填表
返回值

class Solution {
    public int deleteAndEarn(int[] nums) {
        //1. 预处理
        int max = (int)1e4;
        int[] arr = new int[max + 1];
        for(int i = 0; i < nums.length; i++) {
            int index = nums[i];
            arr[index] += index;
        }
        //2. 创建dp表
        //3. 填表
        //4. 返回值
        int[] f = new int[max + 1];
        int[] g = new int[max + 1];
        for(int i = 1; i < max + 1; i++) {
            f[i] = arr[i] + g[i - 1];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[max], g[max]);
    }
}

时空复杂度都为：O(N)

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

4. 粉刷房子

传送门：力扣剑指 Offer II 091. 粉刷房子

题目：

4.1 题目解析

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

4.2 算法原理

4.2.1 状态表示

我们需要通过经验 + 题目要求去决定状态表示：

根据题目的意境以及数据结构，我们得出需要建立二维的dp表（n × 3）
- 也可以三个一维dp表，只不过在这里为了与costs表对应

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

经验：以某个坐标为结尾或者以某个坐标为起点去研究题目问题！

此题用的是“结尾”

再根据经验，一般dp表的其中一值就应该是答案！

所以含义应该就是“最大点数”

综合得到状态表示：dp[i]表示就是起点到坐标为 i 的位置时的这些房子粉刷完的最小花费

而这道题，与之前做过的题不一样的是，一个坐标的状态有三种情况，需要我们继续细化

所以，最终的状态表示为：

dp[i] [0]表示的是，从起点到 i 坐标的这些房子内，i这一个房子为红色情况下的最小花费

dp[i] [1]表示的是，从起点到 i 坐标的这些房子内，i这一个房子为蓝色情况下的最小花费

dp[i] [2]表示的是，从起点到 i 坐标的这些房子内，i这一个房子为绿色情况下的最小花费

4.2.2 状态转移方程

同样的套路，我们需要根据已确定的dp表的值来推导 dp[i][0] dp[i][1] dp[i][2] 的值，并且牢记他们的状态表示！

我们以坐标 i 为结尾
根据“最近一步”去划分问题

“最近一步”可以理解为“必然事件”

此题的“必然事件”就是，到达坐标 i 之前，必然要先到达坐标 i - 1

这个房子如果刷红色的话，那么前一个房子只能是蓝色或者绿色，即花费为dp[i] [1]和dp[i] [2]的较小值加上第i个房子刷红色费用costs[i] [0]
这个房子如果刷蓝色的话，那么前一个房子只能是红色或者绿色，即花费为dp[i] [0]和dp[i] [2]的较小值加上第i个房子刷蓝色费用costs[i] [0]
这个房子如果刷绿色的话，那么前一个房子只能是红色或者蓝色，即花费为dp[i] [0]和dp[i] [1]的较小值加上第i个房子刷绿色费用costs[i] [0]

而1代表着dp[i] [0]表怎么填，2代表着dp[i] [1]表怎么填，3代表着dp[i] [2]表怎么填

所以得出状态转移方程：

dp[i][0] = min{dp[i][1], dp[i][2]} + costs[i][0];

dp[i][1] = min{dp[i][0], dp[i][2]} + costs[i][1];

dp[i][2] = min{dp[i][0], dp[i][1]} + costs[i][2];

4.2.3 初始化

dp[0] [j] = costs[0] [j];

第一个房间花费就是刷对应墙的花费~

4.2.4 填表顺序

从上到下，三列同时填
【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

4.2.5 返回值

最后一个房间刷红刷蓝刷绿三种情况中的较小值~

4.3 编写代码

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

时空复杂度都为：O(N)

【动态规划】简单多状态dp问题（1）打家劫舍问题,剑指offer与算法,动态规划,算法

由于此类问题题目较多，分两篇文章讲述，下一篇文章的题目链接（买卖股票问题）：

传送门：力扣309. 最佳买卖股票时机含冷冻期

传送门：力扣714. 买卖股票的最佳时机含手续费

传送门：力扣123.买卖股票的最佳时机 III

传送门：力扣188. 买卖股票的最佳时机 IV

文章到此结束！谢谢观看
可以叫我小马，我可能写的不好或者有错误，但是一起加油鸭🦆！

本文代码链接：动态规划03/src/Main.java · 游离态/马拉圈2023年6月 - 码云 - 开源中国 (gitee.com)文章来源地址https://www.toymoban.com/news/detail-524079.html

到了这里，关于【动态规划】简单多状态dp问题（1）打家劫舍问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！