提供免费服务器的网站,怎么做电商平台网站,建工e采网,建设单位网站需求报告198.打家劫舍
题目链接#xff1a;
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
求解思路#xff1a;
当前房屋偷与不偷取决于前一个房屋是否被偷了
动规五部曲
确定dp数组及其下标含义#xff1a;考虑下标i#xff08;包括i#xff09…198.打家劫舍
题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
当前房屋偷与不偷取决于前一个房屋是否被偷了
动规五部曲
确定dp数组及其下标含义考虑下标i包括i以内的房屋最多可以偷的金额为dp[i]确定递归公式如果前一个屋子被抢了那么现在这间屋子不能抢即dp[i] dp[i-1]如果前一间屋子没被抢那么这件屋子可以抢即dp[i] dp[i - 2] nums[i]取较大值dp[i] max(dp[i - 2] nums[i], dp[i - 1]);dp数组的初始化递推公式的基础为dp[0]和dp[1]从定义中可以得到dp[0] nums[0],dp[1] max(nums[0], nums[1]);确定遍历顺序dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的从前到后遍历举例推导dp数组以[2,7,9,3,1]为例如图 代码
class Solution {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];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];}
};
213.打家劫舍II
题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
分成两种情况一种是不包含头元素一种是不包含尾元素取较大值即可。
求解思路与上一题一样。
代码
class Solution {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];int r1 robRange(nums, 0, nums.size()-2);int r2 robRange(nums, 1, nums.size()-1);return max(r1, r2);}int robRange(vectorint nums, int start, int end){if (start end) return nums[start];vectorint dp(nums.size());dp[start] nums[start];dp[start1] max(nums[start], nums[start1]);for (int i start2; i end; i){dp[i] max(dp[i-2]nums[i], dp[i-1]);}return dp[end];}
};
337.打家劫舍III
题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
使用一个长度为2的数组记录当前节点偷和不偷所得到的最大金钱
递归动规
确定递归函数的参数和返回值参数为当前节点返回值为一个长度为2的数组其中数组下标为0记录不偷该节点所得到的最大金钱下标为1记录偷该节点所得到的最大金钱确定终止条件遇到空间点无论偷还是不偷都是0返回确定遍历顺序后序遍历二叉树因为要通过递归函数的返回值来做下一步计算确定单层递归逻辑如果偷当前节点则左右孩子都不能投此时val1 cur-val left[0] right[0]如果不偷当前节点则左右孩子可偷可不偷取较大的值此时val2 max(left[0], left[1]) max(right[0], right[1])注意最后返回{val2, val1}即{不偷当前节点得到的最大金钱偷当前节点得到的最大金钱}举例推导dp数组以示例1为例如图 代码
/*** 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:int rob(TreeNode* root) {vectorint result robTree(root);return max(result[0], result[1]);}// 长度为2的数组0表示不偷1表示偷vectorint robTree(TreeNode * cur){if (cur NULL) return vectorint{0,0};vectorint left robTree(cur-left);vectorint 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};}
};
