一条街上若干住户，给出财产，不能抢劫相邻的两家，求最多抢得的钱数。
核心思想：f(n)=Max{f(n−1),f(n−2)+An}
1 class Solution { 2 public: 3 int rob(vector<int>& nums) { 4 if(nums.empty()) return 0; 5 int prepre_fn = 0, pre_fn = 0, fn = 0;//一一对应f(n-2) f(n-1) f(n) 6 int len = nums.size(); 7 for(int i=0;i<len;++i){ 8 fn = max(prepre_fn + nums[i], pre_fn); 9 prepre_fn = pre_fn; 10 pre_fn = fn; 11 } 12 return fn; 13 } 14 };
或者是：
1 class Solution { 2 public: 3 int rob(vector<int>& nums) { 4 if (nums.empty()) return 0; 5 int n1 = 0, n2 = nums[0], len = nums.size(); 6 for (int i = 1; i < len; i++) { 7 int temp = n1; 8 n1 = n2; 9 n2 = max(nums[i] + temp, n1); 10 } 11 return n2; 12 } 13 };
差别不大，只是 f(n-2) f(n-1) f(n)的值互相替换 和 f(n)取值 的顺序有所改变。（这个顺序影响了这三者的初始值）
另i<len比i<nums.size()耗时要短。
原文：http://www.cnblogs.com/co0oder/p/5188312.html