题目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
