你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
示例 1：
輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
示例 2：
輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。
解題思路：
1.房屋個數(shù)小于等于0，返回0
2.房屋個數(shù)小于2，返回房間1
3.房屋個數(shù)小于3的情況下，房間1和房間2哪個多，偷取哪一個
4.如果大于兩間，對于第i（i > 2）間房屋
偷竊第i間時，那么就不能偷竊i-1間，所以偷竊金額應(yīng)為前i-2間總金額最大值和第i間房屋可偷竊金額之和
不偷竊第i間，那么偷竊金額為前i-1間偷竊金額之和
以上兩種選擇應(yīng)該選擇最大值。
如果用dp數(shù)組來表示，則為
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)系，因此只需要用滾動數(shù)組來存儲第i-1間、第i-2間的最大偷竊總金額即可
代碼：
