198. 打家劫舍
你是一個專業(yè)的法外狂徒扭屁，你叫張三，計劃偷竊沿街的房屋荡短。每間房內(nèi)都藏有一定的現(xiàn)金碟嘴，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)鞋既，如果兩間相鄰的房屋在同一晚上被小偷闖入贮配，系統(tǒng)會自動報警谍倦。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 泪勒，一夜之內(nèi)能夠偷竊到的最高金額昼蛀。
思路溯源
方法一：動態(tài)規(guī)劃：
第k間房偷的話，最高金額是前k-2間房的最高金額加上第k間的金額
不偷的話最高是第k-1間房的的最高金額
我們設置一個dp數(shù)組圆存，表示面對第i間房的時候能偷的最大值
- 初始化狀態(tài)：
面對第0間房叼旋，你別無選擇，能偷的最大值就是第0間房
面對第一間房辽剧，你注定只能偷一間送淆，所以最大值是Math.max(nums[0], nums[1])
由于考察任意一件房，只需要知道它前兩間房的最高金額即可怕轿，所以初始狀態(tài)設置完畢 - 對任意間（i）房進行考察
根據(jù)
第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兩間房的信息，所以這里可以做下優(yōu)化
pre就是i-2的最大金額
cur就是-1的最大金額
然后不斷地將這兩個值沿著數(shù)組推進更新
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;
};
方法二：直接自首：
在評論區(qū)看到有人說他直接return 110 自首衫冻。我覺得也應該給分诀紊，非常符合核心價值觀
var rob = function(nums) {
return 110;
};
213. 打家劫舍 II
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋隅俘，每間房內(nèi)都藏有一定的現(xiàn)金邻奠。這個地方所有的房屋都 圍成一圈 笤喳，這意味著第一個房屋和最后一個房屋是緊挨著的。同時碌宴，相鄰的房屋裝有相互連通的防盜系統(tǒng)杀狡，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警 贰镣。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組呜象，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額碑隆。
解法分析：
和法外狂徒一的區(qū)別就是把房子圍成了一圈恭陡，也就是說第一間房和最后一間房能不能偷，他倆現(xiàn)在互相影響了
那咱們有了在上面那個地方的違法經(jīng)歷上煤，現(xiàn)在比較有經(jīng)驗了休玩，我們要考慮如何把這一題分解下，變成和上一題一樣的情景
方法一：
既然題目的變化是成為了一個圈劫狠，那我們就要把圈拆開
分情況討論下：
考察第一間房拴疤，那么可以分兩種情況：假設第一間被偷和假設第一間沒被偷，在dp數(shù)組的開頭和結尾做特殊操作
- 第一間被偷：
那么第一間：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方法用于在一個可以隨便偷的數(shù)組中求最大金額
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
張三又又又拓展了新業(yè)務，這個地區(qū)只有一個入口削罩，我們稱之為 root 瞄勾。
除了 root 之外，每棟房子有且只有一個“父“房子與之相連弥激。一番偵察之后进陡，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果 兩個直接相連的房子在同一天晚上被打劫 微服，房屋將自動報警趾疚。
給定二叉樹的 root 。返回 在不觸動警報的情況下 ，小偷能夠盜取的最高金額 糙麦。
“聰明的小偷發(fā)現(xiàn)這個地方的房屋排列類似于一棵二叉樹”辛孵，這小偷怕不是程序員失業(yè)再就業(yè)
解法分析
偷竊的過程循環(huán)往復，同樣的赡磅，需要用到一個迭代的思想
考察任意一個節(jié)點x魄缚，那么這個節(jié)點有偷與不偷兩種情況
- 當前節(jié)點咱偷
那么兩個子節(jié)點無法偷竊，那么此節(jié)點所能偷到的最大金額就是四個孫子的最大金額之和 - 當前節(jié)點咱不偷
那么兩個子節(jié)點相對來說就比較自由仆邓，可以偷也可以不偷鲜滩。
那么最大金額就是max(左子節(jié)點，右子節(jié)點)- 對于子節(jié)點
能偷的最大金額應當是max(偷此節(jié)點节值，不偷此節(jié)點)
- 對于子節(jié)點
方法：
robInternal方法用于求出某個特定節(jié)點的最大金額徙硅，返回一個數(shù)組，數(shù)組的第0項表示不偷當前節(jié)點可以獲得的最大金額搞疗，第1 項表示偷當前節(jié)點可以獲得的最大金額
var rob = function(root) {
const result = robInternal(root);
return Math.max(result[0], result[1]); //0當前節(jié)點不偷嗓蘑，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桩皿，敬請期待。
