[Leetcode] House Robber, Solution

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.

[Thoughts]
一个dp问题。对于任意一个房子，只有两种状态，rob 或 no_rob.

如果定义 rob[i] 为抢劫house i可获得的最大收益，而no_rob[i] 为不抢劫house i可获得的最大收益，递推关系式可表示为

rob[i] = no_rob[i-1] + house[i];
no_rob[i] = max( rob[i-1], no_rob[i-1]);

如果以 house数组[2,1,1,2]为例，

                            2             1              1               2
            rob           2             1              3               4
           no_rob      0              2             2               3

那么最后的最大收益就是在rob 和no_rob中找个最大的，在此例中就是4


[Code]
实现的时候并不需要真的定义两个数组，用两个临时变量就可以了。

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