珠海网页模板建站,公司网站制作新手教程,衡水企业做网站,天津建设工程信息网专家登录198.打家劫舍
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代表每个…198.打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
1确定dp数组及下标含义
dp[i]考虑下标i以内的房屋最多可以偷窃的金额为dp[i]。
2确定递推公式
决定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房。
然后dp[i]取最大值即dp[i] max(dp[i - 2] nums[i], dp[i - 1])。
3dp数组初始化
从递推公式dp[i] max(dp[i - 2] nums[i], dp[i - 1]);可以看出递推公式的基础就是dp[0] 和 dp[1]
从dp[i]的定义上来讲dp[0] 一定是 nums[0]dp[1]就是nums[0]和nums[1]的最大值即dp[1] max(nums[0], nums[1]);
4确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 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());dp[0]nums[0];dp[1]max(nums[0],nums[1]);for(int i2;inums.size();i) {dp[i]max(dp[i-2]nums[i],dp[i-1]);}return dp[nums.size()-1];}
};
213.打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 能够偷窃到的最高金额。
成环包含三种情况
1不包含首位元素 2包含首元素不包含尾元素 3包含尾元素不包含首元素 class Solution {
public:int rob(vectorint nums) {if(nums.size()0) return 0;if(nums.size()1) return nums[0];int result1robRange(nums,0,nums.size()-2);int result2robRange(nums,1,nums.size()-1);return max(result1,result2);}int robRange(vectorint nums,int start,int end) {if(startend) return nums[start];vectorint dp(nums.size());dp[start]nums[start];dp[start1]max(nums[start],nums[start1]);for(int istart2;iend;i) {dp[i]max(dp[i-2]nums[i],dp[i-1]);}return dp[end];}
};
337.打家劫舍
在上次打劫完一条街道之后和一圈房屋后小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为“根”。 除了“根”之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫房屋将自动报警。
计算在不触动警报的情况下小偷一晚能够盗取的最高金额。
/*** 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:unordered_mapTreeNode*,int umap;int rob(TreeNode* root) {if(rootnullptr) return 0;if(root-leftnullptrroot-rightnullptr) return root-val;if(umap[root]) return umap[root];int val1root-val;if(root-left) val1rob(root-left-left)rob(root-left-right);if(root-right) val1rob(root-right-left)rob(root-right-right);int val2rob(root-left)rob(root-right);umap[root]max(val1, val2);return max(val1, val2);}
};
