house robber 动态规划dp(?)

题目1：

leetcode198 House Robber
在一列数组中找出一个或多个不相邻数，使其值最大。

思路一：

动态规划，设置数组dp[i],存疑当前位置结尾的最大值，再比较出以谁结尾的值最大。
对于这类求极值的问题首先考虑动态规划Dynamic Programming来解，我们维护一个一位数组dp，其中dp[i]表示到i位置时不相邻数能形成的最大和，那么递推公式怎么写呢，我们先拿一个简单的例子来分析一下，比如说nums为{3, 2, 1, 5}，那么我们来看我们的dp数组应该是什么样的，首先dp[0]=3没啥疑问，再看dp[1]是多少呢，由于3比2大，所以我们抢第一个房子的3，当前房子的2不抢，所以dp[1]=3，那么再来看dp[2]，由于不能抢相邻的，所以我们可以用再前面的一个的dp值加上当前的房间值，和当前房间的前面一个dp值比较，取较大值当做当前dp值，所以我们可以得到递推公式dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 由此看出我们需要初始化dp[0]和dp[1]，其中dp[0]即为num[0]，dp[1]此时应该为max(num[0], num[1])

var rob = function(nums) {
    if(nums.length<3){
        if(nums.length==0){
            return 0
        }else if(nums.length==1){
            return nums[0];
        }else if(nums.length==2){
            return Math.max(nums[0],nums[1]);
        }
    }
    var dp=[];
    dp.push(nums[0]);
    dp.push(Math.max(nums[0],nums[1]));
    var res=dp[1];
    for(var i=2;i<nums.length;i++){
        dp.push(Math.max(dp[i-2]+nums[i],dp[i-1]));
        res=Math.max(dp[i],res);
    }
    return res;
};

思路二：核心思想还是用DP，分别维护两个变量a和b，然后按奇偶分别来更新a和b，这样就可以保证组成最大和的数字不相邻

var rob = function(nums) {
    var a=0;
    var b=0;
    for(var i=0;i<nums.length;i++){
        if(i%2===0){
            a=Math.max(a+nums[i],b);
        }else{
            b=Math.max(b+nums[i],a);
        }
    }
    return Math.max(a,b);    
}

题目二：

leetcode213 House Robber II
这道题是之前那道的拓展，现在房子排成了一个圆圈，则如果抢了第一家，就不能抢最后一家，因为首尾相连了，所以第一家和最后一家只能抢其中的一家，或者都不抢，那我们这里变通一下，如果我们把第一家和最后一家分别去掉，各算一遍能抢的最大值，然后比较两个值取其中较大的一个即为所求。那我们只需参考之前的的解题方法，然后调用两边取较大值

• 解法一
  ！注意slice返回子数组，对元数组没有影响，
  splice返回被删除元素，更改元数组

var rob = function(nums) {
     if(nums.length<3){
        if(nums.length==0){
            return 0
        }else if(nums.length==1){
            return nums[0];
        }else if(nums.length==2){
            return Math.max(nums[0],nums[1]);
        }
    }else{
     return Math.max(robLine(nums.slice(1)),robLine(nums.splice(0,nums.length-1)));
    }
};
 function robLine (nums) {
    var dp=[];
    dp.push(nums[0]);
    dp.push(Math.max(nums[0],nums[1]));
    var res=dp[1];
    for(var i=2;i<nums.length;i++){
        dp.push(Math.max(dp[i-2]+nums[i],dp[i-1]));
        res=Math.max(dp[i],res);
    }
    return res;
   }

• 解法二：

var rob=function(nums){
    if(nums.length<3){
        if(nums.length==0){
            return 0
        }else if(nums.length==1){
            return nums[0];
        }else if(nums.length==2){
            return Math.max(nums[0],nums[1]);
        }
    }else{
        return Math.max(robLine(nums.slice(1)),robLine(nums.splice(0,nums.length-1)));
    }
}
function robLine(nums){
    var a=0;
    var b=0;
    for(var i=0;i<nums.length;i++){
        if(i%2===0){
            a=Math.max(a+nums[i],b)
        }else{
            b=Math.max(b+nums[i],a)
        }
    }
      return Math.max(a,b);
}

题目三：

leetcode 337 House Robber III
这个小偷又偷出新花样了，沿着二叉树开始偷，题目中给的例子看似好像是要每隔一个偷一次，但实际上不一定只隔一个

        4
       /
     1
    /
  2
 /
3

思路：????