198.打家劫舍
思路
本题的思路：考虑一个房子要不要偷时不能单凭自己确定，需要看之前的状态，这就是动态规划。
简单的五部曲，记住要考虑周全（尤其是遍历起点、顺序与初始化问题）。
题解
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size(),0);
dp[0] = nums[0];
if(nums.size()>1)dp[1] = max(nums[0],nums[1]);
for(int i = 2;i<nums.size();i++)
{
dp[i] = max(dp[i-1],nums[i]+dp[i-2]);
}
return dp[nums.size()-1];
}
};
213.打家劫舍II
题目链接：213.打家劫舍II
文档讲解：代码随想录
状态：不会，对于首尾相连没有思路，最简单的没想到
思路
与上一题的区别在于首尾相连，两者不能同时取，我的思考方式一直纠结于如何在内部解决环问题。
事实上，内部解决不了，还真得跳出来用笨方法思考。
最优情况仅可能且若有一定存在三种情况的一种，如下：
- 情况一：考虑不包含首尾元素
- 情况二：考虑包含首元素，不包含尾元素
- 情况三：考虑包含尾元素，不包含首元素
两者不能同时取->首随意尾不取+首不取尾随意，三种即可解题，再思考即可化简。
题解
class Solution {
public:
int res(vector<int>& nums)
{
vector<int> dp(nums.size(),0);
dp[0] = nums[0];
if(nums.size()>1)dp[1] = max(nums[0],nums[1]);
for(int i = 2;i<nums.size();i++)
{
dp[i] = max(dp[i-1],nums[i]+dp[i-2]);
}
return dp[nums.size()-1];
}
int rob(vector<int>& nums) {
if(nums.size() == 1)return nums[0];//防止越界
vector<int> nums1(nums.begin(),nums.end()-1);
vector<int> nums2(nums.begin()+1,nums.end());
int result1 = res(nums1);
int result2 = res(nums2);
return result1>result2?result1:result2;
}
};
337.打家劫舍 III
题目链接：337.打家劫舍 III
文档讲解：代码随想录
状态：知道是动规，写不出dp
思路
本题知道是动态规划，关键点是当前状态取决于之前状态的最优值+是否取值两种状态，不能简单将返回值视作单个int。
将所有状态均写入dp以供后面使用，避免重复计算，这就是动态规划。
注意理解本题递归与动态规划复杂度的区别。
题解
class Solution {
public:
//dp[0]不偷 dp[1]偷
vector<int> robtree(TreeNode* cur)
{
if(cur == nullptr)return {0,0};
//一个式子计算4次递归，其实计算一次即可，不然爆内存
//int res1 = cur->val+robtree(cur->left)[0]+robtree(cur->right)[0];
//int res2 = max(robtree(cur->left)[0],robtree(cur->left)[1])+max(robtree(cur->right)[0],robtree(cur->right)[1]);
vector<int> left = robtree(cur->left);
vector<int> right = robtree(cur->right);
int res1 = cur->val+left[0]+right[0];
int res2 = max(left[0],left[1])+max(right[0],right[1]);
return {res2,res1};
}
int rob(TreeNode* root) {
vector<int> result = robtree(root);
if(result[0]>result[1])return result[0];
else return result[1];
}
};