写点什么

LeetCode 题解:213. 打家劫舍 II,动态规划(不缓存偷盗状态),JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 03 月 19 日
LeetCode题解:213. 打家劫舍 II,动态规划(不缓存偷盗状态),JavaScript,详细注释

原题链接:213. 打家劫舍 II


解题思路:


  1. 该题在213. 打家劫舍 II的基础上,将首尾的房屋连接在一起,也就产生了两个场景:


* 偷了第一户,最后一户不能偷,等同于从第一户偷到倒数第二户。

* 偷了最后一户,第一户不能偷,等同于从第二户偷到最后一户。


于是我们可以把房屋分成两段分别处理,然后再将得到的结果一起取最大值即可。

  1. 状态转移方程分析:

* 对于第 i 个房子,有两种场景,偷或不偷:


* 如果不偷的话,dp[i] = dp[i - 1] + 0

* 如果偷的话,那么 i 之前的所有的可能情况,也就是dp[i] = Math.max(nums[i] + dp[i - 2], nums[i] + dp[i - 3], ...)。如此可知,每一位都取了之前所有可能的最大值。那么就可以推导出dp[i - 2] > dp[i - 3] > dp[i - 4]...,因此dp[i - 2]之后的对比都可以省略。

* 状态转移方程:dp[i] = Math.max(dp[i - 1] + 0, nums[i] + dp[i - 2])


/** * @param {number[]} nums * @return {number} */var rob = function (nums) {  // 用dp1递推从0偷到nums.length-2  // 由于要向前递推两层,一次初始化时要创建两个元素,并且都要取最大值  let dp1 = [    // 偷了第0户    nums[0] || 0,    // 第0和1户只能选一户偷    Math.max(nums[0] || 0, nums[1] || 0),  ];
// 从1开始递推到nums.length-2 for (let i = 2; i < nums.length - 1; i++) { dp1[i] = Math.max( // 如果不偷第i户,只需考虑i-1户的情况 dp1[i - 1], // 如果偷第i户,需要考虑i-2到0户的情况,而i-2必然大于之前所有结果,此处只需要考虑i-2即可 dp1[i - 2] + nums[i], ); }
// 用dp2递推从1偷到nums.length-1 // 由于要向前递推两层,一次初始化时要创建两个元素,并且都要取最大值 // 为保证dp2索引和nums能一一对应,dp2[0]存储0占位 let dp2 = [ 0, // 偷了第1户 nums[1] || 0, // 第1和2户只能选一户偷 Math.max(nums[1] || 0, nums[2] || 0), ];
// 从0开始递推到nums.length-1 for (let i = 3; i < nums.length; i++) { dp2[i] = Math.max( // 如果不偷第i户,只需考虑i-1户的情况 dp2[i - 1], // 如果偷第i户,需要考虑i-2到0户的情况,而i-2必然大于之前所有结果,此处只需要考虑i-2即可 dp2[i - 2] + nums[i], ); }
return Math.max(dp1[dp1.length - 1], dp2[dp2.length - 1]);};
复制代码


发布于: 2021 年 03 月 19 日阅读数: 13
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:213. 打家劫舍 II,动态规划(不缓存偷盗状态),JavaScript,详细注释