代码随想录算法训练营第五十天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III
代码随想录算法训练营第五十天
198.打家劫舍
题目链接：198.打家劫舍
- 确定dp数组以及下标的含义：dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
- 确定递推公式：max(dp[i - 1], dp[i - 2] + nums[i]);，不偷当前节点和偷当前节点哪个获利最大就取哪个
- dp数组如何初始化：dp[0]=nums[0]，只有一个必须偷。dp[1]=max(nums[0],nums[1])一共2个元素，只能偷一个最大的
- 确定遍历顺序：从前向后遍历。
- 打印dp数组。
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 1)return nums[0];vector<int> dp(nums.size(), 0);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.size() - 1];}
};
213.打家劫舍II
题目链接：213.打家劫舍II
偷第一家就不能偷最后一家，偷最后一家就不能偷第一家，分别将两种状态求出，再从二者之间找最大值。两种情况分别可以用上题方法求解。
class Solution {
public:int Rob(vector<int>& nums,int start, int end){if(start==end)return nums[start];vector<int> dp(nums.size(), 0);dp[start] = nums[start];dp[start+1] = max(nums[start], nums[start+1]);for (int i = start+2; i <= end; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[end];}int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];int first = Rob(nums,0,nums.size()-2);int last = Rob(nums, 1, nums.size()-1);return max(first,last);}
};
337.打家劫舍III
题目链接：337.打家劫舍III
dp数组表示，每个节点偷当前节点和不偷当前节点可以取得的最大价值。要求当前节点值需要知道左右节点的值，所以是后序遍历。最后再偷根节点和不偷根节点之间取一个最大值即可。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> Rob(TreeNode* cur){if(cur==nullptr)return {0,0};vector<int> left = Rob(cur->left);vector<int> right = Rob(cur->right);vector<int>dp(2);//定义一个dp数组dp[0]表示当前节点不偷可以获得的最大金币,dp[1]表示偷当前节点可以获得的最大金币dp[0] = max(left[0],left[1])+max(right[0],right[1]);//不偷当前节点，那它的子节点可以选择偷或者不偷，左子偷不偷选最大的+右子偷不偷选最大的dp[1] = left[0]+right[0]+cur->val;//偷当前节点，左右子都不能偷，所以等于左不偷+右不偷+当前节点的值return dp;}int rob(TreeNode* root) {return max(Rob(root)[0],Rob(root)[1]);}
};