多状态动态规划之打家劫舍 II

梦里梦外; 2024-03-16 23:50 65阅读 0赞

## 1. 题目分析 ##

题目链接选自力扣 : [打家劫舍 II][II]  
![image.png][]  
根据示例 2 来看 :  
![image.png][image.png 1]  
可以看到, 这个作为 “[打家劫舍 ( 详解链接 )][_ _]” 的变种问题, 除了以下限制还新增了一个限制

1.  相邻房间不能偷
2.  可以从任意位置开始
3.  返回可以偷窃到的最大金额
4.  **新增限制为 : 首尾房间连通, 即选了第一个房间就不能选最后一个房间, 选了最后一个房间就不能选第一个房间**

## 2. 状态表示 ##

以 i 位置为结尾, 表示从某一个位置开始偷窃到 i 位置时的最大偷窃金额, 即 dp\[i\]  
这依然是一个多状态的动态规划问题. 不难发现, 存在以下两种情况

1.  偷窃到 i 位置时, 偷窃 nums\[i\]

这种情况下, 我们用 f\[i\] 表示, 即从某一个位置开始偷窃到 i 位置时, 同时偷窃 nums\[i\] 的最大盗窃金额

1.  偷窃到 i 位置时, 不偷窃 nums\[i\]

这种情况下, 我们用 g\[i\] 表示, 即从某一个位置开始偷窃到 i 位置时, 不偷窃 nums\[i\] 的最大盗窃金额

## 3. 状态转移方程 ##

从前面的状态表示发现, 和 “[打家劫舍 ( 详解链接 )][_ _]” 问题是非常像的. 此时多了一个首尾房间不能同时选的限制. 这时候就有点困难了, 既然和 “[打家劫舍 ( 详解链接 )][_ _]” 问题很像, 那我们能不能把他划分为 " 打家劫舍 " 问题 ?  
依据这个思路, 发现我们可以根据第一个房间偷还是不偷可以划分为两个 “[打家劫舍 ( 详解链接 )][_ _]” 的子问题. **此处我们把 " 打家劫舍 " 方法写作 rob1**

1.  第一个位置偷窃时

![image.png][image.png 2]  
当第一个位置偷窃时, 最后一个位置就不能偷窃了, 并且 1 号房间也不能偷窃了. 因此我们的偷窃的最大金额就为 \[2, n-2\] 区间内.  
这时候的最大偷窃金额也就为 rob1(2, n-2) + nums\[0\]

1.  第一个位置不偷窃时

![image.png][image.png 3]  
当第一个位置不偷窃, 那么最后一个位置就可以偷窃. 这样最大的偷窃金额就在 \[01 n-1\] 区间内  
这时候的最大偷窃金额也就为 rob1(1, n-1)

根据题目要求, 需要的是最大的偷窃金额, 因此最终的转态转移方程则为 **Math.max( rob1(2, n-2) + nums\[0\], rob1(1, n-1) )**

### 3. 1 " 打家劫舍 " 问题状态转移方程 ###

**再来回顾一下 “[打家劫舍 ( 详解链接 )][_ _]” 问题中的状态转移方程**

1.  偷窃到 i 位置时, 偷窃 nums\[i\]

![image.png][image.png 4]  
当偷窃到 i 位置时, 选择偷窃 nums\[i\], 那么 i - 1 位置就是必定不能偷的, 否则会被抓. 因此偷窃到的最大金额就为从某一起始位置偷到 i - 1 之间的最大金额, 并且不偷窃 nums\[i-1\], 这正好对应到我们的转态表示中, 即 g\[i-1\], 最后加上选择偷窃的 nums\[i\]. 最终此时偷窃到 i 位置的最大金额为 **f\[i\] = g\[i-1\] + nums\[i\]**

1.  偷窃到 i 位置时, 不偷窃 nums\[i\]

![image.png][image.png 5]  
当偷窃到 i 位置时, 选择不偷窃 nums\[i\]. 那么这时候 i - 1 位置就有两种情况

1.  i - 1 位置偷 nums\[i-1\]

![image.png][image.png 6]  
这种情况下, 偷窃的最大金额为从某一起始位置到达 i - 1 位置并且偷窃 i - 1 位置的 nums\[i-1\]. 正好对应我们的转态表示 **f\[i-1\].**

1.  i-1 位置不偷

![image.png][image.png 7]  
这种情况下, 偷窃到的最大金额为从某一位置起到达 i - 1 位置并且不偷窃 i - 1 位置的 nums\[i-1\]. 正好对应我们的转态表示 g\[i-1\]

**最终不偷窃 i 位置的 nums\[i\] 的两种情况就分完了, 而我们要的是最大的金额数. 因此最终的状态转移方程为 g\[i\] = Math.max( f\[i - 1\], g \[i - 1\] )**

## 4. 初始化 ##

既然我们已经把问题转为为了 " 打家劫舍 " 的两个子问题. 因此初始化也是根据 " 打家劫舍 " 问题的状态转移方程来初始化  
根据状态转移方程 **g\[i\] = Math.max( f\[i - 1\], g \[i - 1\] 和 f\[i\] = g\[i-1\] + nums\[i\]** 在填写 g\[0\] 和 f\[0\] 位置的时候会存在越界情况.

经过分析, 如果只有一个元素的情况下, 这时候偷窃到这个房间并且选择偷窃 nums\[0\], 最终的最大偷窃金额即位 nums\[0\]. 对应到状态表示中为 f\[i\] = nums\[0\]

同样一个元素的情况下, 偷窃到这个房间时, 可以选择不偷. 最终的最大偷窃金额为 0. 对应到状态表示中为 g\[0\] = 0

## 5. 填表顺序 ##

填表顺序还是一样, 想要知道当前位置的最高偷窃金额, 必须要知道前一个位置的最高偷窃金额. 因此填表顺序为从左往右

## 6. 返回值 ##

按照题目要求返回偷窃到数组末尾 ( n -1 ) 时最大的偷窃金额. 因此要对这两种状态取最大值. 即为 Math.max( g\[n-1\], f\[n-1\] ) ( 注意下标之间的关系 )

## 7. 代码演示 ##

class Solution {
        
        public int rob(int[] nums) {
        
            
            int n = nums.length;
            // 返回两个子问题的 打家劫舍1 的最大值
            // 传入的是闭区间 [2, n-2] [1, n-1] 需要注意
            return Math.max(rob1(nums, 2, n-2) + nums[0], rob1(nums, 1, n-1));
       
        }
    
        private int rob1(int[] nums, int left, int right) {
        
    
            // 判断边界值
            if(left > right) return 0; // 此时数组不存在, 无法偷窃
    
            // 1. 创建 dp 表
            int n = nums.length;
            int[] f = new int[n]; // 表示偷窃到 i 位置时, 偷窃nums[i]
            int[] g = new int[n]; // 表示偷窃到 i 位置时, 不偷窃 nums[i]
    
            // 2. 初始化
            // 此时 left 为这个数组偷窃的第一个位置需要注意
            f[left] = nums[left];
    
            // 3. 填写 dp 表
            // left 位置已经初始化了, 从 left + 1 开始到 right 位置结束
            for(int i = left + 1; i <= right; i++) {
        
                f[i] = g[i-1] + nums[i];
                g[i] = Math.max(f[i - 1], g[i - 1]);
            }
    
            // 4. 确认返回值
            // 返回的是偷窃的数组的最后位置的最大值. 因此为 right 
            return Math.max(g[right], f[right]);
        }   
    }

[II]: https://leetcode.cn/problems/house-robber-ii/
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/11b8c46afcfb4f76827572003540e148.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/660f88493d114ed38581c56cb450c319.png
[_ _]: https://blog.csdn.net/qq_68288689/article/details/131392670?spm=1001.2014.3001.5501
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d6649f4dee85457ba78a06aa4c28cd2c.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9a194bb6266a405791ddce4ee9cf7e28.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/454eb064c90840948ac5e22456009ae7.png
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e848845fd7794547b2f4bce79ebf43b6.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/977340046e1b4bcfbc86027b7937243a.png
[image.png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2c57192757914ed9b29d4760d25c5997.png