你是一個(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)裝置的情況下 摆出，一夜之內(nèi)能夠偷竊到的最高金額朗徊。
示例 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.房屋個(gè)數(shù)小于等于0棚壁，返回0
2.房屋個(gè)數(shù)小于2，返回房間1
3.房屋個(gè)數(shù)小于3的情況下栈虚，房間1和房間2哪個(gè)多袖外，偷取哪一個(gè)
4.如果大于兩間，對(duì)于第i（i > 2）間房屋
偷竊第i間時(shí)魂务，那么就不能偷竊i-1間曼验，所以偷竊金額應(yīng)為前i-2間總金額最大值和第i間房屋可偷竊金額之和
不偷竊第i間，那么偷竊金額為前i-1間偷竊金額之和
以上兩種選擇應(yīng)該選擇最大值粘姜。
如果用dp數(shù)組來(lái)表示鬓照，則為
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
考慮到第i間房屋的最高總金額和第i-1間、第i-2間有關(guān)系孤紧，因此只需要用滾動(dòng)數(shù)組來(lái)存儲(chǔ)第i-1間颖杏、第i-2間的最大偷竊總金額即可
代碼：
