精华内容
下载资源
问答
  • 打家劫舍
    2021-02-16 22:52:52

    打家劫舍
    注解
    f[i]: 第i个元素必选时,能够得到的最大价值。
    g[i]: 第i个元素必不选时,能够得到的最大价值。

    class Solution {
        public int rob(int[] nums) {
            int n = nums.length;
            int[] f = new int[n + 1];
            int[] g = new int[n + 1];
    
            for (int i = 1; i <= n; i ++) {
                f[i] = g[i - 1] + nums[i - 1];
                g[i] = Math.max(f[i - 1], g[i - 1]);
            }
            return Math.max(f[n], g[n]);
        }
    }
    
    更多相关内容
  • leetcode打家劫舍带输入输出 Typescript 与 Javascript 重构技巧 算法 以及 数据结构 练习 环境: typescript: ^4.3.2 ts-node: ^10.0.0 Typescript 语法和类型 学习 : 我的 Leetcode : 数据结构: Leetcode 解题: # ...
  • 1、题目描述 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间...
  • 打家劫舍打家劫舍 III1、题目描述、题目描述在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。除了“根”之外,每栋房子有且只有一个“父“房子...
  • 打家劫舍问题解

    2022-03-23 16:58:38
    打家劫舍问题是动态规划的经典问题,下面将用leetcode里四个例题讲解这个问题。 这个小偷属实是太聪明了,估计是程序员退休转行了。[doge] 第一题 :leetcode 198 打家劫舍I class Solution { public: int rob...

    打家劫舍问题是动态规划的经典问题,下面将用leetcode里四个例题讲解这个问题。

    这个小偷属实是太聪明了,估计是程序员退休转行了。[doge]

    第一题 :leetcode 198 打家劫舍I
    在这里插入图片描述

    class Solution {
    public:
        int rob(vector<int>& nums) {
            //dp数组含义:偷这个房子 则前一个 房子不能偷 即 dp[i] = dp[i - 1] + nums[i]
            //           不偷这个房子 则前前一个可以偷    即 dp[i] = dp[i - 2];  
            // 两者取最大值即可
            int n = nums.size();
            if(n == 1) return nums[0];
            vector<int> dp(n + 1);
            dp[0] = nums[0];
            dp[1] = max(nums[0], nums[1]);//初始化为前两个房子中最大的
            for(int i = 2; i < n; i++){
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
            }
            return dp[n - 1];
        }
    };
    

    第二题 :leetcode 213 打家劫舍II
    在这里插入图片描述

    class Solution {
    public:
        int getmoney(vector<int>& nums, int start, int end){
            //解题思想:和打家劫舍I的区别是这次的房间号是一个环 也就是最后一个房间和第一个房间是连在一起的
            // 此时需要破环(最后一个和第一个只能选择偷一个,所以从这里破) 
            //两种情况:1、去掉最后一个 2、去掉第一个 去掉之后就变成了打家劫舍I了
            if(start == end) return nums[start];
            vector<int> 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(vector<int>& nums) {
            if(nums.size() == 0) return 0;
            if(nums.size() == 1) return nums[0];
            int res1 = getmoney(nums, 0, nums.size() - 2);//去掉最后一个
            int res2 = getmoney(nums, 1, nums.size() - 1);//去掉第一个
            return max(res1, res2);
        }
    };
    

    第三题 :leetcode 337 打家劫舍III
    在这里插入图片描述

    /**
     * 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:
        // {
            //先暴力解法 直接递归计算 money = max(偷父节点的钱, 不偷父节点的钱 + 当前节点的钱)
            // if(root == NULL) return 0;
            // if(root->left == NULL && root->right == NULL) return root->val;
            // //偷父节点 则次父节点的左右孩子不可偷
            // int ans1 = root->val;
            // if(root->left){
            //     ans1 += rob(root->left->left) + rob(root->left->right);
            // }//不偷左孩子
            // if(root->right){
            //     ans1 += rob(root->right->left) + rob(root->right->right);
            // }//不偷右孩子
            // int ans2 = 0;
            // ans2 = rob(root->left) + rob(root->right);
            // return max(ans1, ans2);
            //此法时间复杂度:n^2 时间复杂度:log n 超时了
        //}
        int rob(TreeNode* root){
            vector<int> ans = getmoney(root);
            return max(ans[0], ans[1]);
        }
        //将DP数组初始化为一个int rob(TreeNode* root)只有两个元素的数组 表示偷还是不偷当前结点的最大值
        vector<int> getmoney(TreeNode *cur){
            if(cur == NULL) return vector<int> {0,0};
            //后序遍历
            vector<int> left = getmoney(cur->left);
            vector<int> right = getmoney(cur->right);
            //如果偷当前结点 则左右孩子都不能偷
            int ans1 = cur->val + left[0] + right[0];
            //不偷当前节点,则左右孩子都可以偷
            int ans2 = 0;
            ans2 = max(left[0], left[1]) + max(right[0], right[1]);
            return {ans2, ans1};// 注意ans2是不偷当前节点的最大值 ans1是偷当前节点的最大值,别写反
            //此解法时间复杂度 O(n) 
        }
    };
    

    第四题 :leetcode 740 删除并获得点数
    在这里插入图片描述

    class Solution {
    public:
        int deleteAndEarn(vector<int>& nums) {
        	//这题是打家劫舍问题的变形题
            //分析:如何将元素之间相结合起来,从而推出动规方程
            // dp[i]中的i应该表示的是元素的值而不是下标 因为下标之间没有联系
            int k = nums.size();
            if(k < 1) return 0;
            int maxn = 0;
            for(int i = 0; i < k ;i++){
                maxn = max(maxn, nums[i]);
            }
            vector<int> cntnum(maxn + 1);
            vector<int> dp(maxn + 1);
            for(int i = 0; i < k; i++){
                cntnum[nums[i]]++;
            }
            //此时此刻就变成了打家劫舍问题
            //价值为1的有几个 价值为2的有几个 选了价值为2的就不再选相邻的 1 和 3 即为打家劫舍
            dp[0] = 0;
            dp[1] = cntnum[1];
            for(int i = 2; i <= maxn; i++){
                dp[i] = max(dp[i - 1], dp[i - 2] + cntnum[i] * i);
            }
            return dp[maxn];
        }
    };
    

    以上就是打家劫舍基础问题的解,当然还有很多变形,等以后刷到了在继续更新。

    展开全文
  • 198. 打家劫舍 213. 打家劫舍 II 337. 打家劫舍 III

    198. 打家劫舍

    代码:

    class Solution {	//198. 打家劫舍
    	//动态规划五部曲:
    	//1. 确定dp数组以及下标的含义:下标为i以内的房屋,能够偷窃到的最高金额为dp[i]
    	//2. 确定递推公式:dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
    	//3. dp数组如何初始化:dp[0]=nums[0]  dp[1]=max(nums[0],nums[1])
    	//4. 确定遍历顺序:从前往后
    	//5. 举例推导dp数组:
    public:
    	int rob(vector<int>& nums) {
    		if (nums.size() == 1)return nums[0];
    		vector<int> dp(nums.size());
    		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

    代码:

    class Solution {	//213. 打家劫舍 II  环形的分两种情况,一是不算首元素,二是不算尾元素
    	//动态规划五部曲:
    	//1. 确定dp数组以及下标的含义:下标为i以内的房屋,能够偷窃到的最高金额为dp[i]
    	//2. 确定递推公式:dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
    	//3. dp数组如何初始化:dp[start]=nums[start]  dp[start+1]=max(nums[start],nums[start+1])
    	//4. 确定遍历顺序:从前往后
    	//5. 举例推导dp数组:
    public:
    	int rob(vector<int>& nums) {
    		if (nums.size() == 1)return nums[0];
    		int result1 = robRange(nums, 0, nums.size() - 2);
    		int result2 = robRange(nums, 1, nums.size() - 1);
    		return max(result1, result2);
    	}
    	
    	int robRange(vector<int>& nums, int start, int end) {
    		if (start == end)return nums[start];
    		vector<int> 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 - 2] + nums[i], dp[i - 1]);
    		}
    		return dp[end];
    	}
    };
    

    337. 打家劫舍 III

    代码:

    class Solution {	//337. 打家劫舍 III  树形dp
    	//动态规划五部曲:
    	//1. 确定dp数组以及下标的含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱
    	//2. 确定递推公式:  当前节点的最大金额=max(偷当前节点得到的最大金额,不偷当前节点得到的最大金额)
    	//3. dp数组如何初始化:遇到空节点,返回{0,0}
    	//4. 确定遍历顺序:后序遍历,通过递归左节点,得到偷与不偷的金钱,通过递归右节点,得到偷与不偷的金钱
    	//5. 举例推导dp数组:
    public:
    	vector<int> robTree(TreeNode* cur) {
    		if (cur == nullptr) return vector<int>{0, 0};
    		vector<int> left = robTree(cur->left);
    		vector<int> right = robTree(cur->right);
    		//偷当前节点
    		int val1 = cur->val + left[0] + right[0];
    		//不偷当前节点,左子树的最大值与右子树最大值之和
    		int val2 = max(left[0], left[1]) + max(right[0], right[1]);
    		return{ val2, val1 };
    	}
    	int rob(TreeNode* root) {
    		vector<int> result = robTree(root);
    		return max(result[0], result[1]);
    	}
    };
    

    参考资料:

    代码随想录

    展开全文
  • DP算法——打家劫舍系列

    千次阅读 2022-03-25 15:16:26
    DP算法——打家劫舍系列

    打家劫舍Ⅰ(LeetCode-198)

    1. 问题描述:

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

    2. 示例:

    (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 。

    3. 题解:

    此题要求我们求得一夜之内能够偷窃到的最高金额,这是一个求最优解的问题,而且满足DP三大特性(不清楚的小伙伴可以参考之前的文章:https://blog.csdn.net/m0_51339444/article/details/123716692),因此显然这是一个DP问题。下面我们来看一下规划方程的求解过程:
    在这里插入图片描述
    dp[i]表示以偷i号住户为结尾的最优盗窃方案(i是一定要偷的),可能对这里有些疑惑,那我解释一下:任何一种偷法肯定不可能一家都不偷,既然偷了,那最优解肯定以偷某家为最后一家,我们只需要依次求出以偷i为结尾的最优盗窃方案,最后对dp数组取max即可。
    如上图所示:偷i了,就不可能偷i-1,上一个最优子问题有可能是以偷i-2为结尾的,也可能是i-3,但是思考一下能不能是偷i-4呢? Impossible! 因为如果上一个子问题是以i-4结尾,那研究的是dp[i],那就会违背最优化原则,因为你偷了i-4,为什么不偷i-2和i,而只偷i ? 显然不合理。因此我们只需要考虑dp[i-2]和dp[i-3],规划方程如下:
    `
    dp[i] = max(dp[i - 2] + nums[i], dp[i - 3] + nums[i])

    然后我们解决一下DP边界问题,很容易理解:
    dp[0] = nums[0]; dp[1] = nums[1]; dp[2] = nums[0] +nums[2];

    4. 代码:

    class Solution {
    public:
    
        int rob(vector<int>& nums) {
            int len = size(nums);
            int dp[len];
            if(len>=1)
                dp[0] = nums[0];
            if(len>=2)
                dp[1] = nums[1];
            if(len>=3)
                dp[2] = nums[0] + nums[2];
            for(int i = 3; i < len; ++i)
            {
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 3] + nums[i]);
            }
            sort(dp, dp + len);
            return dp[len-1];
        }
    };
    

    打家劫舍Ⅱ(LeetCode-213)

    1. 问题描述:

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

    2. 示例:

    (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

    3. 题解:

    在这里插入图片描述
    我们刚才做了打家劫舍1,不能白做,是吧~~ 那就要想办法把打家劫舍2变成1。看下上图的分界线,如果偷0的话,那就不能偷n-1,就可以讲问题转化为求0 to n-2的最优解问题。如果不偷0,那问题就转化为1 to n-1的最优解问题。之后不做赘述,还没理解的uu可以康康代码。 代码不简洁因为想增强可读性。

    4. 代码:

    class Solution {
    public:
        int rob(vector<int>& nums) {
            int len = nums.size();
            // 不偷第一家房子
            int dp1[len];
            memset(dp1, 0, len*sizeof(int));
            // if(len >= 1)
            //     dp1[0] = 0;
            if(len >= 2)
                dp1[1] = nums[1];
            if(len >= 3)
                dp1[2] = nums[2];
            if(len > 3)
                dp1[3] = nums[1] + nums[3];
            if(len > 4)
            {
                 for(int i = 4; i < len; ++i)
                {
                    dp1[i] = max(dp1[i-2] + nums[i], dp1[i - 3] + nums[i]);
                }
            }
            sort(dp1, dp1 + len);
            int max1 = dp1[len - 1];
            // 偷第一家
            int dp2[len];
            memset(dp2, 0, len*sizeof(int));
            if(len >= 1) 
                dp2[0] = nums[0];
            if(len >= 2)
                dp2[1] = -100;
            if(len == 3)
                dp2[2] = -100;
            if(len > 3)
                dp2[2] = nums[0] + nums[2];
            if(len > 4)
            {
                 for(int i = 3; i < len - 1; ++i)
                {
                    dp2[i] = max(dp2[i-2] + nums[i], dp2[i - 3] + nums[i]);
                }
            }
            sort(dp2, dp2 + len);
            int max2 = dp2[len - 1];
            int MAX = max(max1, max2);
            return MAX;
        }
    };
    
    

    打家劫舍Ⅲ(删除并获得点数)(LeetCode-740)

    1. 问题描述:

    给你一个整数数组 nums ,你可以对它进行一些操作。每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

    2. 示例:

    (1)

    输入:nums = [3,4,2]
    输出:6
    解释:
    删除 4 获得 4 个点数,因此 3 也被删除。
    之后,删除 2 获得 2 个点数。总共获得 6 个点数。

    (2)

    输入:nums = [2,2,3,3,3,4]
    输出:9
    解释:
    删除 3 获得 3 个点数,接着要删除两个 2 和 4 。
    之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。
    总共获得 9 个点数。

    3. 题解:

    这道题看似和前两题毫无关系,但是我们还是可以想办法转化成类似的问题。首先,这道题有个隐藏点:当我们选择了nums[i]这个数,那么我们就相当于获得了nums中所有等于nums[i]的点数,因为我们可以重复这个操作,但是代价是放弃nums中所有等于nums[i]-1和nums[i]+1的点数(类似前两题中的不能偷相邻两个住户)。
    我们可以构建一个cnt数组,索引即数值,对应元素大小为该数值的个数。
    规划方程为:
    dp[i] = max(dp[i - 1], dp[i - 2] + cnt[i] * i)
    边界条件为: dp[0] = 0; dp[1] = 1*cnt[1];

    4. 代码:

    class Solution {
    public:
        int deleteAndEarn(vector<int>& nums) {
            int len = nums.size();
            if(len < 1)
                return 0;
            int maxn = 0;
            for(int i = 0; i < len; ++i)
            {
                maxn = max(maxn, nums[i]);
            }
            int cnt[maxn + 1];
            memset(cnt, 0, (maxn + 1)*sizeof(int));
            int dp[maxn + 1];
            memset(dp, 0, (maxn + 1)*sizeof(int));
            for(int i = 0; i < len; ++i)
            {
                int k = nums[i];
                cnt[k]++;
            }
            dp[0] = 0;
            dp[1] = 1*cnt[1];
            for(int i = 2; i <= maxn; ++i)
            {
                dp[i] = max(dp[i - 1], dp[i - 2] + cnt[i] * i);
            }
            return dp[maxn];
        }
    };
    
    
    
    展开全文
  • 打家劫舍问题
  • 文章目录 题目1——打家劫舍一 解题思路 代码实现 题目2——打家劫舍二 解题思路 代码实现 题目1——打家劫舍一 你是一个经验丰富的小偷,准备偷沿街的一排房间,每个房间都存有一定的现金,为了防止被发现,你不能...
  • 动态规划解决打家劫舍问题 1. 打家劫舍 题目描述 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一...
  • 打家劫舍问题总结打家劫舍问题总结
  • 打家劫舍问题汇总

    2022-04-01 19:36:08
    打家劫舍 II198. 打家劫舍 ①dp数组定义: dp[i]代表前i个房子在满足条件下的能偷窃到的最高金额。 ②问题情况: 如果将nums[i] 加入最终的结果中那么nums[i-1]将不能加入——>dp[i] = dp[i-2] + nums[i] ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,672
精华内容 3,468
关键字:

打家劫舍

友情链接: Clk50M_div_1HZ.rar