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

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

1. 题目分析



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

049cfc7f941de2655b5a7b6faa34cba5.png根据示例 2 来看 :

4d6f35e0b8f6e8ec999f74e758e8b54d.png


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

  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. 第一个位置偷窃时

35b1968db532b177cd26c9c6060d6b96.png

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

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


  1. 第一个位置不偷窃时

a1c9eaf0027af6dd1590f6cb42e9fdbf.png

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

b75ffd58b67e0fbf01c7a1d2ddde0231.png

当偷窃到 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]

bd5739ad27d17ffb090eea83002be061.png


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


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

84b8bb30bd84525fabcfc87e74ffd448.png

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


  1. i-1 位置不偷

64e29760aa6ffeaed0dcfc25813c95a9.png

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


相关文章
|
7月前
|
机器学习/深度学习 消息中间件 Kubernetes
动态规划-线性DP问题总结(一)
动态规划-线性DP问题总结(一)
|
7月前
|
消息中间件 Kubernetes NoSQL
动态规划-状态压缩、树形DP问题总结
动态规划-状态压缩、树形DP问题总结
【动态规划】198. 打家劫舍
【动态规划】198. 打家劫舍
【动态规划刷题 1 】 第N个泰波那契数&& 三步问题
【动态规划刷题 1 】 第N个泰波那契数&& 三步问题
|
7月前
|
消息中间件 Kubernetes NoSQL
动态规划-线性DP问题总结(二)
动态规划-线性DP问题总结(二)
|
7月前
力扣740. 删除并获得点数(动态规划)
力扣740. 删除并获得点数(动态规划)
|
7月前
|
算法
动态规划之第 N 个泰波那契数/三步问题【leetCode】【算法】
动态规划之第 N 个泰波那契数/三步问题【leetCode】【算法】
【动态规划入门】动态规划思路五部曲_斐波那契_爬楼梯_最小花费爬楼梯
【动态规划入门】动态规划思路五部曲_斐波那契_爬楼梯_最小花费爬楼梯
71 0
|
算法
【学会动态规划】打家劫舍 II(12)
【学会动态规划】打家劫舍 II(12)
28 0
|
存储 Cloud Native Go
198. 打家劫舍:动态规划
这是 力扣上的 198. 打家劫舍,难度为 中等。