当前位置：首页 > article >正文

动态规划算法：13.简单多状态 dp 问题_打家劫舍II_C++

article 2024/11/19 12:55:09

题目链接：LCR 090. 打家劫舍 II - 力扣（LeetCode）

一、题目解析

题目：

解析：

由题目可知，小偷不可以偷相邻的两个房间，并且题目告诉我们第一个房间是和第二个房间相连的，所以小偷偷完第一个房间，就不可以偷最后一个房间。

这与上一道打家劫舍问题相比，这个题目需要我们多考虑首尾相连问题

我们拿示例1举例：

只有三个房间，小偷如果先偷第一个房间，那么就不可以偷第二个第三个房间，所以只能偷第二个房间才能使获取金钱数到达最大

二、算法原理

1、状态表示

我们在状态表示的时候，一般都会创建一个数组dp，也就是我们所说的dp表，我们要做的就是把每一个状态的值填入这个表内，最终这个表内的某一个值可能就是我们要返回的值。

状态简单理解就是dp表内某一个值代表的含义。

如何确定状态表示

题目要求

简单的题目里一般会给出

经验+题目要求

越学越深入，动态规划也是熟能生巧，在题目中没有明显给出的时候，我们就要凭借自己做题的经验来确定，所以就需要我们大量的做题。

分析问题的过程中，发现重复子问题

分析问题的过程中把重复子问题抽象成我们的状态表示，这个更难理解，一切的基础都是我们先对动态规划算法熟练运用。我也不懂，我们慢慢来。

综上：我们通常会以一个位置为结尾或者开始求得我们想要的答案

那我们的这道题得状态表示是什么样的：

根据经验，我们仍以一个位置为结尾做题

状态表示：dp[i]表示到达i位置时获取的金钱数达到最大

2、状态转移方程

确定状态表示之后我们就可以根据状态标识推出状态转移方程

状态转移方程是什么？

不讲什么复杂的，简单来说状态转移方程就是 dp[i]等于什么 dp[i]=？

这个就是状态转移方程，我们要做的，就是推出dp[i]等于什么

我们根据状态表示再结合题目+经验去推理转移方程，这一步也是我们整个解题过程中最难的一步

我们在这道题先简单了解下什么是状态转移方程，之后比较难的题目再细推

状态转移方程推理：

1、i位置状态分析

我们知道，当小偷到达i位置时有两种状态，一种是偷，一种是不偷

我们令在i位置偷时金钱数达到最大值得情况为f[i],不偷时的情况为g[i]，原房间金钱数数组为nums

2、首尾状态分析

当小偷从第一个位置开始偷时，就不可以偷最后一个房间，范围为1到n-1(n为房间数)

当小偷从第二个位置偷时，就可以偷最后一个房间，范围为2到n

我们分析的首尾两种状态是本道题的两种大状态，因为小偷只能这样做抉择，不然就会报警，所以说，我们最终的答案要要从这两种状态里选择一个最大值

我们把首尾相连的问题化成了两种状态，所以我们在这两种状态里就不用在考虑首尾相连的问题，我们就可以把这两种状态变成我们之前做过的打家劫舍I，上一篇写过

打家劫舍I文章链接：动态规划算法：12.简单多状态 dp 问题_打家劫舍_C++-CSDN博客

3、初始化

我们创建dp表就是为了把他填满，我们初始化是为了防止在填表的过程中越界

怎么谈越界？

我们在填f[0]时，我们会发现，到达该位置前的f[-1]位置根本不存在

dp表初始化:

这里不用对dp表做特殊初始化

特殊位置初始化：

仍是打家劫舍I的初始化问题

f[0]=nums[0]
g[0]=0

4、填表顺序

从左到右依次填表，两个表同时填写

5、返回值

这里的返回值，是我们两种状态所求的值作比较后返回的一个较大的值

三、编写代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
//两种状态最比较，返回最大值
        return max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
    }   
//另写一个打家劫舍I的函数，三个参数分别是，原数组，左下标，右下标
    int rob1(vector<int>&nums,int left,int right)
{
//比较两个下标大小，左下标如果大于有下标择返回0，针对于数组大小很小的特殊情况
    if(left>right)return 0;
    int n=nums.size();
//1、创建dp表
    vector<int> f(n);
    auto g=f;
//2、初始化
    f[left]=nums[left];
//3、填表
    for(int i=left+1;i<=right;i++)
    {
        f[i]=g[i-1]+nums[i];
        g[i]=max(f[i-1],g[i-1]);
    }
//4、返回该状态的最大值
    return max(f[right],g[right]);
}
};