最开始的想法,没有考虑到0和n-1不能同时取的情况。
const int N = 110;
class Solution {
public:
int dp[N];
int rob(vector<int>& nums) {
int n = nums.size();
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i <= n; i++){
dp[i] = max(dp[i-2] + nums[i-1], dp[i-1]);
}
return dp[n];
}
};
看了视频解说,要考虑状态转移,也比较好分别考虑取第一个点和不取第一个点。
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
vector<vector<int>> f(n, vector<int>(2));
//选第0个
f[0][0] = INT_MIN; f[0][1] = nums[0];
for(int i = 1; i < n; i++){
f[i][0] = max(f[i-1][0], f[i-1][1]);
f[i][1] = f[i-1][0] + nums[i];
}
int sum1 = f[n-1][0];
//不选第0个
f[0][0] = 0; f[0][1] = INT_MIN;
for(int i = 1; i < n; i++){
f[i][0] = max(f[i-1][0], f[i-1][1]);
f[i][1] = f[i-1][0] + nums[i];
}
int sum2 = max(f[n-1][0], f[n-1][1]);
return max(sum1, sum2);
}
};