建设学分银行网站策划书,自己做网站前端开发,网站建设目标与期望,自建网站 服务器目录
198. 打家劫舍
问题描述#xff1a;
实现代码与解析#xff1a;
动态规划#xff08;版本一#xff09;#xff1a;
原理思路#xff1a;
动态规划#xff08;版本二#xff09;#xff1a;
原理思路#xff1a;
213. 打家劫舍 II
问题描述#xff1a…目录
198. 打家劫舍
问题描述
实现代码与解析
动态规划版本一
原理思路
动态规划版本二
原理思路
213. 打家劫舍 II
问题描述
实现代码与解析
动态规划
原理思路
337. 打家劫舍 III
问题描述
实现代码与解析
动态规划树形dp 原理思路 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 。
实现代码与解析
动态规划版本一
class Solution {
public:int rob(vectorint nums){//先把前两个单独弄出来返回if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];//dp含义, 按顺序偷第 i 个屋子时获得的最大金额vectorint dp(nums.size(), 0);//dp数组dp[0] nums[0]; // 初始化dp[1] nums[1];//遍历for (int i 2; i nums.size(); i){//小于 3 的时候只能跳一个所以单独计算一下喽if (i 3) dp[i] dp[i - 2] nums[i];else{//跳一个或则跳两个不能再多跳了不然肯定会少偷这两之间取最大喽dp[i] max(dp[i - 2] nums[i], dp[i - 3] nums[i]);// 偷 i - 2的屋子时获得的最大金额加上此屋子的金额,和偷 i - 3 的屋子时获得的最大金额加上此屋子金额取最大}}int result max(dp[nums.size() - 1], dp[nums.size() - 2]);//倒数第一个和倒数第二个比较因为最后偷的肯定是这两个房间之一return result;}
};
原理思路 这里dp数组的含义是偷第 i 个屋子后能获得的最大价值有点像爬梯子大家看注释就能懂但是其实是写的麻烦了所以大家看版本二就可以了要简洁很多。
动态规划版本二
class Solution {
public:int rob(vectorint nums){//先把前两个单独弄出来返回if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];//dp含义, 按顺序选择0~i的屋子是否偷取时获得的最大金额vectorint dp(nums.size(), 0);//dp数组//初始化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];}
};
原理思路 这里dp数组的含义是在1 ~ i 之间选择能获取的最大金额。 所以房间有两种状态一种是偷那么我们就找出 i - 1 能获取的最大金额然后加上 nums[ i ]就为此时的如果偷的最大金额一种是不偷那么我们肯定是偷了 i - 1 编号的房间此时dp[ i - 1] 为不偷的最大价值两个之间进行比较就求出了对于 i 房间偷或不偷选择出的最大金额也就是dp[ i ]了。
213. 打家劫舍 II
问题描述 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
示例 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
实现代码与解析
动态规划
class Solution {
public:int robRange(vectorint nums,int start,int end){if(start end) return nums[start];// 只有一种元素vectorint dp(nums.size());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(vectorint nums) {if(nums.size() 0) return 0;if(nums.size() 1) return nums[0];int result1 robRange(nums, 0, nums.size() - 2); // 不选取最后有一个房间的最大价值int result2 robRange(nums, 1, nums.size() - 1); // 不选取第一个房间的最大价值int result max(result1, result2);return result;}
};
原理思路 相比于打家劫舍Ⅰ了一个限制条件就是房屋练成环了所以无非就两种情况一种是首尾两个房间都不偷一种是首尾两个房间偷其中一个根据Ⅰ的思路我们只要算出不选取最后一个房间的最大金额和不选取第一个房间的最大金额两个之中取最大就可以了所以就比Ⅰ多了个选最大的操作而已其他相似照着写就行。
337. 打家劫舍 III
问题描述 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。
除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。
示例 1: 输入: root [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 3 1 7
示例 2: 输入: root [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 5 9s
实现代码与解析
动态规划树形dp
class Solution {
public://dp数组含义0为不偷cur房间1为偷cur房间vectorint robTree(TreeNode* cur){//没有房间返回0if(cur NULL) return vectorint{0,0};//左右子树偷或不偷的最大金额vectorint leftDp robTree(cur - left);vectorint rightDp robTree(cur - right);int value1 leftDp[0] rightDp[0] cur - val;// 此房间偷那么其子树肯定不偷int value2 max(leftDp[0], leftDp[1]) max(rightDp[0], rightDp[1]);//不偷cur此时判断其左右子树偷或不偷的最大值不要认为一定偷子树就为最大值一定要比较一下return {value2, value1};}int rob(TreeNode* root) {vectorint result robTree(root);return max(result[0], result[1]);}
}; 原理思路 这里房间的连接变为二叉树的连接方式了题目描述还是相连接的不能一起偷。 这里我们的dp数组的含义就发生改变了dp为一个长度为2的数组dp[ 0 ]表示不偷当前房间的最大金额dp[ 1 ]表示偷当前房间的最大金额并且作为返回值。 首先偷当前房间的递推公式好写偷此房间那么其孩子结点一定不偷
dp[ 1 ] leftDp[0] rightDp[0] cur - val; 而不偷当前房间的话我们就要比较孩子结点偷或不偷的最大金额了取最大注意不要认为偷孩子结点就是最大金额这是一个误区一定要比较一下万一孩子结点的孩子结点和大于孩子结点呢此时的递推公式为
dp[ 0 ] max(leftDp[0], leftDp[1]) max(rightDp[0], rightDp[1]); 还有就是这里肯定是后序遍历我们要知道孩子结点的信息。
