力扣打家劫舍系列总结

198.打家劫舍 &＃xff1a;你是一个专业的小偷&＃xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&＃xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&＃xff0c;如果两间相邻的房屋在同一晚上被小偷闯入&＃xff0c;系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组&＃xff0c;计算你 不触动警报装置的情况下 &＃xff0c;一夜之内能够偷窃到的最高金额。

第i间累积的金额&＃xff1a;

当前房间不偷&＃xff0c;延续前一间的金额  dp[i-1]

当前房间偷&＃xff0c;前提是前一间不偷&＃xff0c;dp[i-2]&＃43;n[i]

初始化dp[0]和dp[1]

213&＃xff0c;打家劫舍II :这道题目和198.打家劫舍 (opens new window)是差不多的&＃xff0c;唯一区别就是成环了。

选头不选尾&＃xff0c;或者选尾不选头

Dd(0,len-2)  dd(1,len-1)  需要排除len为0&＃xff0c;1&＃xff0c;2的情况

337&＃xff0c;打家劫舍 III &＃xff1a;除了“根”之外&＃xff0c;每栋房子有且只有一个“父“房子与之相连。一番侦察之后&＃xff0c;聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫&＃xff0c;房屋将自动报警。

采用后序

//不偷(不管子节点偷不偷&＃xff0c;取子节点最大的值)

let val1&＃61;Math.max(left[0],left[1])&＃43;Math.max(right[0],right[1])

//偷&＃xff08;取当前节点的值&＃xff0c;和子节点不偷的值&＃xff09;

let val2&＃61;root.val&＃43;left[0]&＃43;right[0