1. 题目分析

题目链接选自力扣 : 打家劫舍 II

根据示例 2 来看 :

可以看到, 这个作为 “打家劫舍 ( 详解链接 )” 的变种问题, 除了以下限制还新增了一个限制

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

2. 状态表示

以 i 位置为结尾, 表示从某一个位置开始偷窃到 i 位置时的最大偷窃金额, 即 dp[i]

这依然是一个多状态的动态规划问题. 不难发现, 存在以下两种情况

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

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

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

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

3. 状态转移方程

从前面的状态表示发现, 和 “打家劫舍 ( 详解链接 )” 问题是非常像的. 此时多了一个首尾房间不能同时选的限制. 这时候就有点困难了, 既然和 “打家劫舍 ( 详解链接 )” 问题很像, 那我们能不能把他划分为 " 打家劫舍 " 问题 ?

依据这个思路, 发现我们可以根据第一

个房间偷还是不偷可以划分为两个 “打家劫舍 ( 详解链接 )” 的子问题. 此处我们把 " 打家劫舍 " 方法写作 rob1

1. 第一个位置偷窃时

当第一个位置偷窃时, 最后一个位置就不能偷窃了, 并且 1 号房间也不能偷窃了. 因此我们的偷窃的最大金额就为 [2, n-2] 区间内.

这时候的最大偷窃金额也就为 rob1(2, n-2) + nums[0]

2. 第一个位置不偷窃时

当第一个位置不偷窃, 那么最后一个位置就可以偷窃. 这样最大的偷窃金额就在 [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]

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

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

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

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

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

2. i-1 位置不偷

这种情况下, 偷窃到的最大金额为从某一位置起到达 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]);
    }   
}