07
04/2015
[LeetCode] House Robber
House Robber
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.
解题思路：
动态规划。d[i]=max(d[i-2]+num[i], d[i-1]); 这两种情况分别代表倒数第2间房不偷，倒数第二间房偷的最大钱数。注意边界的情况。下面是代码：
class Solution {
public:
int rob(vector<int> &num) {
int len=num.size();
if(len==0){
return 0;
}
if(len==1){
return num[0];
}
if(len==2){
return max(num[0], num[1]);
}
int* d=new int[len];
d[0]=num[0];
d[1]=max(num[0], num[1]);
for(int i=2; i<len; i++){
d[i]=max(d[i-2]+num[i], d[i-1]);
}
int result=d[len-1];
delete[] d;
return result;
}
private:
int max(int a, int b){
return a>b?a:b;
}
};二次刷题（2015-08-07）
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if(len == 0){
return 0;
}
if(len == 1){
return nums[0];
}
int d[len];
d[0] = nums[0];
d[1] = max(nums[0], nums[1]);
for(int i=2; i<len; i++){
d[i] = max(nums[i] + d[i-2], d[i-1]);
}
return d[len-1];
}
};转载请注明：康瑞部落 » [LeetCode] House Robber
0 条评论