198. House Robber

Let dp[i] be the maximal treasure the thief can steel in house i. So the state transition is dp[i] = max(dp[i-1], nums[i-2]+nums[i]). The initial state will be dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

1:  class Solution {  
2:  public:  
3:    int rob(vector<int>& nums) {  
4:      int n = nums.size();  
5:      if (n == 0) return 0;  
6:      if (n == 1) return nums[0];  
7:      if (n == 2) return max(nums[0], nums[1]);  
8:      vector<int> dp(n, 0);  
9:      dp[0] = nums[0];  
10:      dp[1] = max(nums[0], nums[1]);  
11:      for (int i = 2; i < n; i++) {  
12:        dp[i] = max(dp[i-1], dp[i-2]+nums[i]);  
13:      }  
14:      return dp[n-1];  
15:    }  
16:  };