#
一天一道LeetCode本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处
##（一）题目
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.
##（二）解题
题目大意：一个专业小偷，现在有一排房子给他偷，他不能偷相邻的两个房子，不难会报警，每个房子里有一笔钱，请问怎么偷，才能偷到最多的钱！
换成数学问题就是，给定一个数组a[n]，要从里面取数出来求和，相邻的两个数不能一起取，怎么取数才能使和最大！
解题思路：对于一个数a[i]来说，有两种情况，取和不取，取的话当前和为a[i]+sum[i-2]，不取的话为sum[i-1]。其中sum为i位置能取得的最大和。
基于以上思路，很容易写出一下非递归版本代码：
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
vector<int> curmaxNum(nums.size()+1,0);//大小为size+1
curmaxNum[0] = 0;//不偷第一个数
curmaxNum[1] = nums[0];//偷第一个数，这么写为了避免处理边界问题
for(int i = 2 ; i < nums.size()+1 ; i++)
{
//rob：curmaxNum[i-2]+nums[i-1]
//notrob：curmaxNum[i-1]
curmaxNum[i] = max(curmaxNum[i-1],curmaxNum[i-2]+nums[i-1]);//这里为num[i-1]是因为前面约定好的
}
return curmaxNum[nums.size()];
}
};
下面时递归版本代码：
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> curmaxNum(nums.size(),-1);
return dprob(nums,0,curmaxNum);
}
int dprob(vector<int>& nums , int cur ,vector<int>& curmaxNum)
{
if(cur>=nums.size()) return 0;
if(curmaxNum[cur]!=-1) return curmaxNum[cur];//表示以及算过，直接返回
//rob
int havarob = nums[cur] + dprob(nums,cur+2,curmaxNum);//偷的情况
//not rob
int rob = dprob(nums,cur+1,curmaxNum);//不偷的情况
curmaxNum[cur]=max(havarob,rob);//记录中间值
return max(havarob,rob);//返回较大的值
}
};