?

題意：有一個整數序列，從中挑出一些數字，使得總和是最大，前提是，相鄰的兩個數字中只能挑其一。比如1 2 3 就只能挑2或者1和3。

思路：很直觀的題，dp思想。降低規模，從小規模開始考慮。如果只有兩個數字，那么結果很明顯就能知道是其中之大者。假如已經知道了第 i 個之前的決策，那么第i+2個之前的決策也就知道了。前兩個數字已經由人工得知，設為dp[0]和dp[1]，那么dp[2]=max(dp[0]+nums[2], dp[1])。狀態轉移方程dp[i]=max(dp[i-1], dp[i-2]+num[i] )。

這里有狀態壓縮的思想，只不過狀態只有兩個，0和1代表前一個數字是否被挑出。即dp數組的下標，1代表i-1個之前的決策結果，也代表了第i-1個已經挑出，所以第i個不能再挑出來了；但是0代表i-2個之前的決策結果，也代表了i-1個不挑出。

?

1 class Solution { 2 public: 3 int rob(vector<int>& nums) { 4 if(nums.empty()) return 0; 5 if(nums.size()==1) return nums[0]; 6 if(nums.size()==2) return max(nums[1],nums[0]); 7 8 int dp[2]; 9 dp[0]=nums[0]; //初始化也是很重要的 10 dp[1]=max(nums[0],nums[1]); 11 12 for(int i=2; i<nums.size(); i++) 13 { 14 int tmp=max(dp[1],dp[0]+nums[i]); 15 dp[0]=dp[1];//往前移。因為dp[0]已經沒作用了 16 dp[1]=tmp; 17 } 18 return dp[1]; 19 } 20 }; AC代碼

?

轉載于:https://www.cnblogs.com/xcw0754/p/4498047.html

總結

以上是生活随笔為你收集整理的LeetCode House Robber 家庭劫犯（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。