打家劫舍

力扣題目鏈接
dp含義：考慮偷下標(biāo)為0-i的房間時(shí)，能偷的最大金額
遞推公式：
偷或不偷當(dāng)前房間：
偷：dp[i-2]+nums[i]。不能偷i-1房間的，因?yàn)橄噜彙?br> 不偷：dp[i-1]
dp[i]=Max(dp[i-2]+nums[i],dp[i-1])
初始化：
由遞推公式，可看出i>=2,因此需要初始化dp[0],dp[1]
dp[0]=nums[0],dp[1]=Max(nums[1],nums[0])

var rob = function(nums) {
    let dp = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[1], nums[0]);

    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[nums.length - 1];
};

打家劫舍II

力扣題目鏈接

與打家劫舍的區(qū)別：最后一個(gè)房間，若選擇，則第一個(gè)房間不能選。
分析：
拆分成三種情況：
1.不考慮首位元素

2. 不考慮尾元素

3. 不考慮首元素

   
   
   image.png
   
   
   image.png
   
   
   image.png

但2，3情況包含情況1。因此，最終所求應(yīng)為2，3情況取最大值。

var rob = function(nums) {
    console.log(robAss(nums.slice(1)))
    console.log(robAss(nums.slice(0,nums.length-1)))
    if(nums.length ===1){
        return nums[0]
    }
    return Math.max(robAss(nums.slice(1)),robAss(nums.slice(0,nums.length-1)))

};
function robAss(nums){
    const len = nums.length;
    // dp數(shù)組初始化
    const dp = [nums[0], Math.max(nums[0], nums[1])];
    // 從下標(biāo)2開始遍歷
    for (let i = 2; i < len; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[len - 1];
}

打家劫舍III

樹形dp題目
力扣題目鏈接

1. dp數(shù)組（dp table）以及下標(biāo)的含義：下標(biāo)為0記錄不偷該節(jié)點(diǎn)所得到的的最大金錢，下標(biāo)為1記錄偷該節(jié)點(diǎn)所得到的的最大金錢。
   確定遍歷順序
2. 遍歷順序。后序遍歷。 因?yàn)橐ㄟ^遞歸函數(shù)的返回值來做下一步計(jì)算。

var rob = function(root) {
    var postOrder = node=>{
        if(!node) return [0,0]

        let left= postOrder(node.left)
        let right=postOrder(node.right)
        Do = node.val+left[0]+right[0]
        DoNot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [DoNot,Do]
    }

    return Math.max(postOrder(root)[0],postOrder(root)[1])
};