本題是動態規劃問題。

第一步，明確并理解dp數組以及下標的含義

dp[i]表示從第0號房間一直到第i號房間(包含第i號房間)可以偷到的最大金額，具體怎么偷這里不考慮，第i+1號及之后的房間也不考慮。換句話說，dp[i]也就是只考慮[0,i]號房間，無論怎么偷可以偷到的最大金額。

按照這個定義，dp[n-1]就是答案。需要注意的是，dp[i]一定能求到值，不代表一定是偷了第i號房間才求得dp[i]。

第二步，明確并理解遞推公式

考慮第i號房間，只有兩種可能，偷或者不偷。

偷第i號房間，則第i-1號房間肯定不能偷，此時能獲得的總金額為dp[i] = dp[i-2] + nums[i]。

不偷第i號房間，此時dp[i]應該等于dp[i-1]。

第三步，理解dp數組如何初始化

dp[0]應該初始化為第0號房間的金額。因為只有一間房的時候，能偷到的最大金額顯然就是把它偷了。

dp[1]，含義是從第0號房間和第1號房間偷，能偷到的最大金額。由于相鄰的房間不能都偷，所以dp[1]= max(nums[0],numd[1]);

i>=2的dp[i]可以不初始化，或者說無論初始化為多大都沒關系，因為dp[i]只和dp[i-1],dp[i-2],nums[i]有關系。

第四步，理解遍歷順序

因為dp[i]依賴于它前面的dp[i-1]和dp[i-2]，所以i的遍歷順序肯定要從小到大。

代碼

按照上面的思路，先初始化dp[0]和dp[1]，再讓i從2開始遍歷，含義更加明確，代碼更好理解，如下所示：

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();//dp[i]表示從第0號房間一直到第i號房間(包含第i號房間)可以偷到的最大金額。//按照這個定義，dp[n-1]就是答案vector<int> dp(n);dp[0] = nums[0];if(n < 2)return dp[0];dp[1] = max(nums[0],nums[1]);for(int i = 2;i < n;i++){//偷第i號房間int temp1 = dp[i-2] + nums[i];//不偷第i號房間int temp2 = dp[i-1];dp[i] = max(temp1,temp2);}return dp[n-1];}
};

但實際上，也可以不初始化讓i從0開始遍歷，代碼如下所示：

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();//dp[i]表示從第0號房間一直到第i號房間(包含第i號房間)可以偷到的最大金額。//按照這個定義，dp[n-1]就是答案vector<int> dp(n);for(int i = 0;i < n;i++){//偷第i號房間int temp1 = (i >= 2 ? dp[i-2]:0) + nums[i];//不偷第i號房間int temp2 = i >= 1 ? dp[i-1]:0;dp[i] = max(temp1,temp2);}return dp[n-1];}
};