198. 打家劫舍
你是一个专业的法外狂徒，你叫张三，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
思路溯源
方法一：动态规划：
第k间房偷的话，最高金额是前k-2间房的最高金额加上第k间的金额
不偷的话最高是第k-1间房的的最高金额
我们设置一个dp数组，表示面对第i间房的时候能偷的最大值
- 初始化状态：
面对第0间房，你别无选择，能偷的最大值就是第0间房
面对第一间房，你注定只能偷一间，所以最大值是Math.max(nums[0], nums[1])
由于考察任意一件房，只需要知道它前两间房的最高金额即可，所以初始状态设置完毕 - 对任意间（i）房进行考察
根据
第k间房偷的话，最高金额是前k-2间房的最高金额加上第k间的金额
不偷的话最高是第k-1间房的的最高金额
所以第i间的最大金额就是dp[i - 2] + nums[i]和dp[i - 1]里面取最大值
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
var rob = function(nums) {
const len = nums.length
let dp = [nums[0], Math.max(nums[0], nums[1])] //如果长度是1，这里Math.max(nums[0], nums[1])是NaN，不会报错
if(len === 1 ) return dp[0]
if(len === 2 ) return dp[1]
for(let i = 2; i < len; i++){
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
}
return dp[len - 1]
};
由于我们真正需要的只有i-1和i-2两间房的信息，所以这里可以做下优化
pre就是i-2的最大金额
cur就是-1的最大金额
然后不断地将这两个值沿着数组推进更新
var rob = function(nums) {
const len = nums.length;
let pre = 0; // i-2的最大金额
let cur = 0; //i-1 的最大金额
for (let i = 0; i < len; i++) {
const next = Math.max(pre + nums[i], cur); //当前房屋的最大金额
pre = cur; //这两个值向前推进
cur = next;
}
return cur;
};
方法二：直接自首：
在评论区看到有人说他直接return 110 自首。我觉得也应该给分，非常符合核心价值观
var rob = function(nums) {
return 110;
};
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
解法分析：
和法外狂徒一的区别就是把房子围成了一圈，也就是说第一间房和最后一间房能不能偷，他俩现在互相影响了
那咱们有了在上面那个地方的违法经历，现在比较有经验了，我们要考虑如何把这一题分解下，变成和上一题一样的情景
方法一：
既然题目的变化是成为了一个圈，那我们就要把圈拆开
分情况讨论下：
考察第一间房，那么可以分两种情况：假设第一间被偷和假设第一间没被偷，在dp数组的开头和结尾做特殊操作
- 第一间被偷：
那么第一间：dp[0] = nums[0]
第二间一定不能偷,所以：dp[1] = nums[0]
最后一间只能是不被偷，所以:dp[n] = dp[n-1] - 第一间没有被偷
那么第一件不能被偷：dp[0] = 0
var rob = function(nums) {
const len = nums.length
if(len === 1 ) return nums[0]
if(len === 2 ) return Math.max(...nums)
//第一间被偷：所以最后一间只能是不被偷，所以dp[n] = dp[n-1]
let dp = [nums[0], nums[0]]
for(let i = 2; i < len; i++){
if(i === len - 1){
dp[i] = dp[i - 1]
} else {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
}
}
//第一间没被偷,所以dp[0] = 0
dp1 = [0, Math.max(0, nums[1])]
for(let i = 2; i < len; i++){
dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1])
}
return Math.max(dp[len - 1], dp1[len - 1 ])
};
方法二：
分两种情况：第一间没被偷和最后一间没被偷
第一间没被偷，意味着第2~n间你随便偷
第n间没被偷，意味着第1~n-1间你随便偷
那么为什么这两种情况包含了所有的可能呢？
在所有情景中可以分为第1和第n间房都被偷了（条件不允许，排除）和第1和第n间房至少有一个没被偷两种情况
第1和第n间房至少有一个没被偷两种情况分为：1偷n不偷，n偷1不偷，两个都不偷。
能被这两种情况覆盖：第1间没被偷、第n间没被偷
所以我们就在，这两种情况的最大金额中求最大值即可
var rob = function(nums) {
const len = nums.length
if(len === 1 ) return nums[0]
if(len === 2 ) return Math.max(nums[0], nums[1])
//1~n-1随便偷 nums.slice(0,len -1)
//2~n随便偷 nums.slice(1,len)
return Math.max(get(nums.slice(1,len)), get(nums.slice(0,len -1)))
function get(nums){ //get方法用于在一个可以随便偷的数组中求最大金额
const len = nums.length
let dp = [nums[0], Math.max(nums[0], nums[1])]
if(len === 1 ) return dp[0]
if(len === 2 ) return dp[1]
for(let i = 2; i < len; i++){
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
}
return dp[len - 1]
}
};
337. 打家劫舍 III
张三又又又拓展了新业务，这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
“聪明的小偷发现这个地方的房屋排列类似于一棵二叉树”，这小偷怕不是程序员失业再就业
解法分析
偷窃的过程循环往复，同样的，需要用到一个迭代的思想
考察任意一个节点x，那么这个节点有偷与不偷两种情况
- 当前节点咱偷
那么两个子节点无法偷窃，那么此节点所能偷到的最大金额就是四个孙子的最大金额之和 - 当前节点咱不偷
那么两个子节点相对来说就比较自由，可以偷也可以不偷。
那么最大金额就是max(左子节点，右子节点)- 对于子节点
能偷的最大金额应当是max(偷此节点，不偷此节点)
- 对于子节点
方法：
robInternal方法用于求出某个特定节点的最大金额，返回一个数组，数组的第0项表示不偷当前节点可以获得的最大金额，第1 项表示偷当前节点可以获得的最大金额
var rob = function(root) {
const result = robInternal(root);
return Math.max(result[0], result[1]); //0当前节点不偷，1偷
};
function robInternal(root){
let result = [0, 0]
if(root != null){
let left = robInternal(root.left)
let right = robInternal(root.right)
result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
result[1] = left[0] + right[0] + root.val
}
return result
}
2560. 打家劫舍 IV
法外狂徒张三由于技艺精湛还有编程思维，所以目前还没被抓到，有机会再跟大家分享打家劫舍IV，敬请期待。
