題目鏈接：
https://leetcode-cn.com/problems/house-robber/description/
你是一個(gè)專業(yè)的小偷淋叶，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警危尿。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下馁痴，能夠偷竊到的最高金額谊娇。
示例 1:
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)罗晕。
偷竊到的最高金額 = 1 + 3 = 4 济欢。
示例 2:
輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)赠堵，接著偷竊 5 號(hào)房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 法褥。
解題思路
1茫叭、首先想一想如果是暴力如何做？
假設(shè)從最后一家店鋪開始搶半等，那么只會(huì)遇到2種情況揍愁，即：搶這家店和下下家店，或者不搶這家店杀饵。所以我們得到遞歸的公式:
Math.max(solve(nums,index-1),solve(nums,index-2)+nums[index]);
2莽囤、上面的暴力算法雖然能夠得到正確的結(jié)果，但是顯然遞歸的效率是很低的切距，如果有n家店鋪朽缎，每家店鋪有2種可能，那么時(shí)間復(fù)雜度就是2的n次方蔚舀。那么如何優(yōu)化呢？
我們分析一下：
如果我們開始搶的是第n-1家店锨络，那么后面可以是（n-3,n-4,n-5,n-6....）;
如果我們開始搶的是第n-2家店赌躺，那么后面可以是（n-4,n-5,n-6,....）;
那么這兩種情況顯然n-3之后的n-4,n-5,n-6,....都重復(fù)計(jì)算了。顯然這里有非常大的優(yōu)化空間羡儿。通常我們使用空間來(lái)?yè)Q時(shí)間礼患，即用一個(gè)數(shù)組記錄每次計(jì)算的結(jié)果，這樣每次情況只需要計(jì)算一次掠归，再次遇到只需直接返回結(jié)果即可缅叠，大大優(yōu)化了時(shí)間。
代碼如下：
class Solution {
public static int[] result;
public int solve(int[] nums,int index){
if(index < 0){
return 0;
}
if(result[index] >= 0){
return result[index];
}
result[index]=Math.max(solve(nums,index-1),solve(nums,index-2)+nums[index]);
return result[index];
}
public int rob(int[] nums) {
result = new int[nums.length];
for(int i=0;i<nums.length;i++){
result[i]=-1;
}
return solve(nums,nums.length-1);
}
}
總結(jié)
這道題就是動(dòng)態(tài)規(guī)劃虏冻，其本質(zhì)是在遞歸的思想上進(jìn)行優(yōu)化肤粱。
原問題（N）-->子問題（N-1）-->原問題（N）
最優(yōu)子結(jié)構(gòu)
1、子問題最優(yōu)決策可導(dǎo)出原問題的最優(yōu)決策厨相。
2领曼、無(wú)后效性
重疊子問題
1、去冗余
2蛮穿、空間換時(shí)間
