[LeetCode] House Robber
The first version:
class Solution {
public:
int rob(vector<int>& nums) {
switch(nums.size()) {
case 0:
return 0;
case 1:
return nums[0];
case 2:
return max(nums[0], nums[1]);
}
int *dp = new int[nums.size() + 1];
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i <= nums.size(); i++) {
dp[i] = max(nums[i - 1] + dp[i - 2], dp[i - 1]);
}
int result = dp[nums.size()];
delete[] dp;
return result;
}
};
We noticed that only the message of dp[i-1] and dp[i-2] is used, so we can improve this.
Second version:
class Solution {
public:
int rob(vector<int>& nums) {
switch(nums.size()) {
case 0:
return 0;
case 1:
return nums[0];
}
int dp_0 = nums[0];
int dp_1 = 0;
int dp_2 = 0;
int tmp;
for(int i = 1; i < nums.size(); i++) {
dp_2 = dp_1;
dp_1 = dp_0;
dp_0 = max(nums[i] + dp_2, dp_1);
}
return dp_0;
}
};
It's also very slow now.I wonder how to optimize it.