198.打家劫舍
终于没借助任何提示，自己写出来了。
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp (nums.size()+1,0);
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]);
}
return dp[nums.size()];
}
};
213.打家劫舍II
这道题我想的思路是给用了首元素的组合都做上记号。如果最后一个元素用了首元素，那么就取dp倒数第二位的值。但这个方法经过提交后，发现是有错误的。可能有些逻辑上错误。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 1){
return nums[0];
}
vector<int> dp(nums.size(),0);
vector<bool> stat(nums.size(),false);
stat[0] = true;
dp[0] = nums[0];
if(nums[1] < nums[0]){
stat[1] = true;
dp[1] = nums[0];
}
else{
dp[1] = nums[1];
}
for(int i=2;i<nums.size(); i++){
if(dp[i-2]+nums[i] > dp[i-1]){
dp[i] = dp[i-2]+nums[i];
stat[i] = stat[i-2];
}
else{
dp[i] = dp[i-1];
stat[i] = stat[i-1];
}
}
if(stat[nums.size()-1] && nums.size()>2){
return max(dp[nums.size()-1]-nums[0],dp[nums.size()-2]);
}
else{
return dp[nums.size()-1];
}
};
};
下面的是我根据Carl的文字讲解理解了，自己写出来的。
做动态规划题的时候，总会遇到访问不正确内存的时候，原因就是我的for loop里的边界设的不对。就像是这次，我就是忘了把for loop里的起始点设为start+2，因为我们已经初始化过前两个值，所以就没必要从前两个值开始遍历，遍历的话反而会访问错误的内存。
class Solution {
public:
vector<int> robhelper(vector<int>& nums,int start, int end){
cout<<start<<" "<<end<<endl;
vector<int> res(nums.size(),0);
res[start] = nums[start];
res[start+1] = max(nums[start],nums[start+1]);
for(int i=start+2; i<end; i++){
res[i] = max(res[i-2]+nums[i],res[i-1]);
}
return res;
}
int rob(vector<int>& nums) {
if(nums.size() == 1){
return nums[0];
}
if(nums.size() == 2){
return max(nums[0],nums[1]);
}
vector<int> no_first = robhelper(nums,1,nums.size());
vector<int> no_last = robhelper(nums,0,nums.size()-1);
return max(no_first[nums.size()-1],no_last[nums.size()-2]);
}
};
337.打家劫舍III
把这两个融合到了一起，可真是够难的。我自己没写出来。好绕啊。
class Solution {
public:
int rob(TreeNode* root) {
vector<int> result = robTree(root);
return max(result[0], result[1]);
}
// 长度为2的数组，0：不偷，1：偷
vector<int> robTree(TreeNode* cur) {
if (cur == NULL) return vector<int>{0, 0};
vector<int> left = robTree(cur->left);
vector<int> right = robTree(cur->right);
// 偷cur，那么就不能偷左右节点。
int val1 = cur->val + left[0] + right[0];
// 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};
}
};
