LeetCode 198. 【DP】打家劫舍
原题链接
简单
作者:
大明湖的鱼
,
2021-01-14 11:25:45
,
所有人可见
,
阅读 270
动态规划
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
if(n == 1) return nums[0]; //没人或者只有一户时的返回值
int dp[n]; //dp表示到达该房子所能盗窃的最大金额
dp[0] = nums[0]; //只有一户人家
dp[1] = max(nums[0] , nums[1]); //只有两户人家
for(int i = 2 ;i < n ;i++){
dp[i] = max(dp[i-1],dp[i-2] + nums[i]);//不偷或者偷
}
return dp[n-1];
}
};
只用到了dp[i-1] 和 dp[i-2],可用滚动数组优化空间至$O(1)$
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
if(n == 1) return nums[0]; //没人或者只有一户时的返回值
int dp[n]; //dp表示到达该房子所能盗窃的最大金额
dp[0] = nums[0]; //只有一户人家
dp[1] = max(nums[0] , nums[1]); //只有两户人家
int a = dp[0];
int b = dp[1];
for(int i = 2 ;i < n ;i++){
int tmp = max(b,a + nums[i]);//不偷或者偷
a = b;
b = tmp;
}
return b;
}
};