You are a PRofessional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

s思路： 1. 用dp.從“不能搶相鄰兩家的錢”這個條件入手，例如：

如上圖，cur表示當(dāng)前位置時搶或不搶的最大值，pre表示前一個位置搶或不搶中最大。那么第二天當(dāng)前位置有7，這就要比較了：如果搶，則總共就是7+上一個位置的pre,即：7+0=7；不搶，則就是上一個位置的cur=5，max(7,5)=7,遞推關(guān)系：pre=cur, cur=max(cur,pre+nums[i])。 2. 為什么這類題可以用dp?首先，求最值問題，很多都可以考慮用dp，這個還不關(guān)鍵。最關(guān)鍵的是，搶到最多錢是個過程，且在過程中要一直保存搶到做多，就應(yīng)為這個，我們可以把全程搶最多分割成n個小任務(wù)。又根據(jù)條件“不能搶相鄰兩家的錢”，這些任務(wù)之間還有聯(lián)系，根據(jù)這個關(guān)系來得到遞推關(guān)系即可！ 3. “不能搶相鄰兩家的錢”，根據(jù)這個條件，說明只需要維護(hù)兩個狀態(tài)，當(dāng)前位置和前一個位置的最大，然后不斷更新當(dāng)前和前一個位置。