参考文章均来自代码随想录
LeetCode 198 打家劫舍
参考文章链接
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2： 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。- dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
- 决定dp[i]的因素就是第i房间偷还是不偷。如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，（注意这里是考虑，并不是一定要偷i-1）然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
- dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);
- dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历
classSolution{public:introb(vector<int>&nums){if(nums.size()==0)return0;if(nums.size()==1)returnnums[0];vector<int>dp(nums.size()+1,0);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(inti=2;i<nums.size();i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}returndp[nums.asize()-1];}};时间复杂度: O(n)
空间复杂度: O(n)
LeetCode 213 打家劫舍 ||
参考文章链接
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1： 输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。 示例 2： 输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 3： 输入：nums = [1,2,3] 输出：3成环后有三种情况：
情况一是首尾都不考虑
情况二是只考虑首
情况三是只考虑尾
而情况二和情况三包含情况一
情况三虽然是考虑包含尾元素，但不一定要选尾部元素
所以求情况二和情况三后取最大值即可 每个情况都是打家劫舍的流程
classSolution{public:introbRange(vector<int>&nums,intstart,intend){if(end==start)returnnums[start];vector<int>dp(nums.size());dp[start]=nums[start];dp[start+1]=max(nums[start],nums[start+1]);for(inti=start+2;i<=end;i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}returndp[end];}introb(vector<int>&nums){if(nums.size()==0)return0;if(nums.size()==1)returnnums[0];intresult1=robRange(nums,0,nums.size()-2);// 情况二intresult2=robRange(nums,1,nums.size()-1);// 情况三returnmax(result1,result2);}};时间复杂度: O(n)
空间复杂度: O(n)
LeetCode 337 打家劫舍 |||
参考文章链接
力扣题目链接
本题属于树形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) {} * }; */classSolution{public:introb(TreeNode*root){vector<int>result=robTree(root);returnmax(result[0],result[1]);}// 长度为2的数组，0：不偷，1：偷vector<int>robTree(TreeNode*cur){if(cur==NULL)returnvector<int>{0,0};vector<int>left=robTree(cur->left);vector<int>right=robTree(cur->right);// 偷cur，那么就不能偷左右节点。intval1=cur->val+left[0]+right[0];// 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况intval2=max(left[0],left[1])+max(right[0],right[1]);return{val2,val1};}};时间复杂度：O(n)，每个节点只遍历了一次
空间复杂度：O(log n)，算上递推系统栈的空间
