文章目录
-
- 原题题目
- 代码实现（首刷自解）
- 代码实现（二刷自解 DAY 203 C++）
- 代码实现（三刷自解 DAY 311 C++）
原题题目
代码实现（首刷自解）
int rob(int* nums, int numsSize){
int i,max1 = 0,max2 = 0;int* dp1 = (int*)malloc(sizeof(int) * (numsSize+1));int* dp2 = (int*)malloc(sizeof(int) * (numsSize+1));memset(dp1,0,sizeof(int) * (numsSize+1));memset(dp2,0,sizeof(int) * (numsSize+1));dp1[0] = dp2[0] = dp2[1] = 0;for(i=1;i<=numsSize;i++){
if(i == 1) dp1[i] = nums[i-1];else if(i == 2) dp1[i] = dp2[i] = nums[i-1];else{
if(i != numsSize) dp1[i] = fmax(dp1[i-3],dp1[i-2]) + nums[i-1];dp2[i] = fmax(dp2[i-3],dp2[i-2]) + nums[i-1];}max1 = fmax(max1,dp1[i]);max2 = fmax(max2,dp2[i]);}return fmax(max1,max2);
}
代码实现（二刷自解 DAY 203 C++）
class Solution {
public:int rob(vector<int>& nums) {
if(nums.empty()) return 0;int pre1 = nums[0],pre2 = 0,now = 0,ret = 0;for(int i = 1;i < nums.size()-1;++i){
now = max(pre2+nums[i],pre1);pre2 = pre1;pre1 = now;}ret = max(pre1,pre2);if(nums.size() < 2) return ret;pre1 = nums[1],pre2 = 0;for(int i = 2;i < nums.size();++i){
now = max(pre2+nums[i],pre1);pre2 = pre1;pre1 = now; }return max(ret,max(pre1,pre2));}
};
代码实现（三刷自解 DAY 311 C++）
class Solution {
public:int rob(vector<int>& nums) {
vector<int> dp(nums.size() + 2, 0);int ret = nums[0];dp[0] = nums[0], dp[1] = (nums.size() >= 2 ? max(nums[0], nums[1]) : 0);if (nums.size() >= 2) ret = max(ret, dp[1]);for (int i = 2; i < nums.size() - 1; ++i) {
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);ret = max(ret, dp[i]);}dp[0] = 0, dp[1] = (nums.size() >= 2 ? nums[1] : 0);for (int i = 2; i < nums.size(); ++i) {
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);ret = max(ret, dp[i]);}return ret;}
};