題目1：
leetcode198 House Robber
在一列數(shù)組中找出一個(gè)或多個(gè)不相鄰數(shù)战转，使其值最大。
思路一：
動(dòng)態(tài)規(guī)劃以躯，設(shè)置數(shù)組dp[i],存疑當(dāng)前位置結(jié)尾的最大值槐秧，再比較出以誰結(jié)尾的值最大。
對(duì)于這類求極值的問題首先考慮動(dòng)態(tài)規(guī)劃Dynamic Programming來解忧设，我們維護(hù)一個(gè)一位數(shù)組dp刁标，其中dp[i]表示到i位置時(shí)不相鄰數(shù)能形成的最大和，那么遞推公式怎么寫呢址晕，我們先拿一個(gè)簡單的例子來分析一下膀懈，比如說nums為{3, 2, 1, 5}，那么我們來看我們的dp數(shù)組應(yīng)該是什么樣的谨垃，首先dp[0]=3沒啥疑問启搂，再看dp[1]是多少呢，由于3比2大刘陶，所以我們搶第一個(gè)房子的3胳赌，當(dāng)前房子的2不搶，所以dp[1]=3匙隔，那么再來看dp[2]疑苫，由于不能搶相鄰的，所以我們可以用再前面的一個(gè)的dp值加上當(dāng)前的房間值，和當(dāng)前房間的前面一個(gè)dp值比較捍掺，取較大值當(dāng)做當(dāng)前dp值撼短，所以我們可以得到遞推公式dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 由此看出我們需要初始化dp[0]和dp[1]，其中dp[0]即為num[0]挺勿，dp[1]此時(shí)應(yīng)該為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曲横，分別維護(hù)兩個(gè)變量a和b，然后按奇偶分別來更新a和b满钟，這樣就可以保證組成最大和的數(shù)字不相鄰
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
這道題是之前那道的拓展胜榔，現(xiàn)在房子排成了一個(gè)圓圈，則如果搶了第一家湃番，就不能搶最后一家夭织，因?yàn)槭孜蚕噙B了，所以第一家和最后一家只能搶其中的一家吠撮，或者都不搶尊惰，那我們這里變通一下，如果我們把第一家和最后一家分別去掉泥兰，各算一遍能搶的最大值弄屡，然后比較兩個(gè)值取其中較大的一個(gè)即為所求。那我們只需參考之前的的解題方法鞋诗，然后調(diào)用兩邊取較大值
- 解法一
膀捷！注意slice返回子數(shù)組，對(duì)元數(shù)組沒有影響削彬，
splice返回被刪除元素全庸，更改元數(shù)組
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
這個(gè)小偷又偷出新花樣了，沿著二叉樹開始偷融痛，題目中給的例子看似好像是要每隔一個(gè)偷一次壶笼，但實(shí)際上不一定只隔一個(gè)
4
/
1
/
2
/
3
