写点什么

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

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

原题链接:https://leetcode-cn.com/problems/house-robber-ii/


解题思路:


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


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

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


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

  1. 状态转移方程分析:

* 对于第i户人家,有偷和不偷两种可能。

* 如果偷,i - 1户人家只能不偷。

* 如果不偷,i - 1户人家偷不偷都可以,此时取i - 1户两个状态的最大值即可。

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

* 偷到最后一户时,只需要取其最大值,就是最高金额。


/** * @param {number[]} nums * @return {number} */var rob = function (nums) {  // 用dp1递推从0偷到nums.length-2,初始值是第0户偷与不偷的状态  let dp1 = [[nums[0] || 0, 0]];
// 从1开始递推到nums.length-2 for (let i = 1; i < nums.length - 1; i++) { dp1[i] = [ // 如果偷当前人家,那么上一户人家就不能偷,只能取不偷的值 dp1[i - 1][1] + nums[i], // 如果不偷当前人家,上一户人家偷不偷都可以,只需要取一个最大值 Math.max(dp1[i - 1][0], dp1[i - 1][1]), ]; }
// 用dp2递推从1偷到nums.length-1,初始值是第1户偷与不偷的状态 // 为保证dp2索引和nums能一一对应,dp2[0]存储一个空数组占位 let dp2 = [[], [nums[1] || 0, 0]];
// 从0开始递推到nums.length-1 for (let i = 2; i < nums.length; i++) { dp2[i] = [ // 如果偷当前人家,那么上一户人家就不能偷,只能取不偷的值 dp2[i - 1][1] + nums[i], // 如果不偷当前人家,上一户人家偷不偷都可以,只需要取一个最大值 Math.max(dp2[i - 1][0], dp2[i - 1][1]), ]; }
// 两次递推结果的最大值,就是最终结果 return Math.max(...dp1[dp1.length - 1], ...dp2[dp2.length - 1]);};
复制代码


发布于: 2021 年 02 月 22 日阅读数: 14
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

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