云南网站设计公司,网站死链接检查,怎么开发自己的网站,wordpress html 过滤LeetCode 198.打家劫舍
题目链接#xff1a;198.打家劫舍
踩坑#xff1a;很多坑#xff0c;自动把它当作背包问题了#xff0c;但其实这就是一个普通的动态规划题目#xff0c;背包问题本质上是一个二维问题#xff0c;只是可以简化成一维#xff0c;想要抽象为背包问…LeetCode 198.打家劫舍
题目链接198.打家劫舍
踩坑很多坑自动把它当作背包问题了但其实这就是一个普通的动态规划题目背包问题本质上是一个二维问题只是可以简化成一维想要抽象为背包问题首先就是要明确背包大小物品重量物品价值。而本题的dp数组的含义是dp[i]:[0, i]家能偷到的最大价值其中并不涉及到背包大小。
思路
dp数组含义dp[i][0, i]家能偷到的最大价值递推公式dp[i] max(dp[i - 2] nums[i], dp[i-1])初始化dp[0] nums[0]; dp[1] max(nums[0], nums[1]);遍历顺序从小到大
代码
class Solution {
public:int rob(vectorint nums) {if(nums.size() 1) return nums[0];if(nums.size() 2) return max(nums[0], nums[1]);vectorint 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-2] nums[i], dp[i-1]);}return dp[nums.size()-1];}
};LeetCode 213.打家劫舍II
题目链接213.打家劫舍II
踩坑真给卡哥说中了一有环就不知道从哪里开始哪里结束。
思路首尾相接带来的变化就是首尾只能选择一个或者都不选一共三种情况。然而首尾只选其一包含了二者都不选的情况所以只需要分别计算不选头不选尾的两种情况并取最大即可。
代码
class Solution {
public:int rob(vectorint nums) {if(nums.size() 1) return nums[0];if(nums.size() 2) return max(nums[0], nums[1]);vectorint dp(nums.size()-1, 0);dp[0] nums[0];dp[1] max(nums[0], nums[1]);for(int i 2; i nums.size()-1; i){dp[i] max(dp[i-1], dp[i-2]nums[i]);}int result1 dp[nums.size()-2];dp[0] nums[1];dp[1] max(nums[2], nums[1]);for(int i 2; i nums.size()-1; i){dp[i] max(dp[i-1], dp[i-2]nums[i1]);}int result2 dp[nums.size()-2];return max(result1, result2);}
};LeetCode 337.打家劫舍III
题目链接337.打家劫舍III
踩坑想到了暴力解法但是超时了。。。苦呀西
思路关键在于dp数组的定义在暴力解法中递归函数的返回值是该节点能偷到的最大值。举例节点A返回从该节点出发能偷到的最大值B是其父节点。如果从B出发想知道不偷A能得到的最大值就不得不重新遍历A的子树超时也是因为大量这样的重复计算。所以如果节点返回的是一个数组里面有从该节点出发偷该节点能得到的最大值与不偷该节点能得到的最大值的话就可以解决这个问题。
代码
/*** 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:vectorint tracking(TreeNode* root){if(root nullptr) return vectorint{0, 0};vectorint left tracking(root-left);vectorint right tracking(root-right);int val1 max(left[0], left[1]) max(right[0], right[1]);int val2 left[0] right[0] root-val;return vectorint{val1, val2};}int rob(TreeNode* root) {vectorint result tracking(root);return max(result[0], result[1]);}
};
