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.從“不能搶相鄰兩家的錢”這個條件入手，例如：
| num | 5 | 7 | 10 | 2 | 9 | 13 |
|---|---|---|---|---|---|---|
| cur | 5 | 7 | 15 | 15 | 24 | 28 |
| pre | 0 | 5 | 7 | 15 | 15 | 24 |
如上圖，cur表示當前位置時搶或不搶的最大值，pre表示前一個位置搶或不搶中最大。那么第二天當前位置有7，這就要比較了：如果搶，則總共就是7+上一個位置的pre,即：7+0=7；不搶，則就是上一個位置的cur=5，max(7,5)=7,遞推關系：pre=cur, cur=max(cur,pre+nums[i])。 2. 為什么這類題可以用dp?首先，求最值問題，很多都可以考慮用dp，這個還不關鍵。最關鍵的是，搶到最多錢是個過程，且在過程中要一直保存搶到做多，就應為這個，我們可以把全程搶最多分割成n個小任務。又根據條件“不能搶相鄰兩家的錢”，這些任務之間還有聯系，根據這個關系來得到遞推關系即可！ 3. “不能搶相鄰兩家的錢”，根據這個條件，說明只需要維護兩個狀態，當前位置和前一個位置的最大，然后不斷更新當前和前一個位置。
//方法1：dpclass Solution {public: int rob(vector<int>& nums) { // if(nums.empty()) return 0; int pre=0,cur=nums[0]; for(int i=1;i<nums.size();i++){ int tmp=max(cur,pre+nums[i]); pre=cur; cur=tmp; } return cur; }};新聞熱點
疑難解答
