代码随想录训练营Day 50|力扣198.打家劫舍、213.打家劫舍II、337.打家劫舍III

2024-06-05 12:52

本文主要是介绍代码随想录训练营Day 50|力扣198.打家劫舍、213.打家劫舍II、337.打家劫舍III,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.打家劫舍

视频讲解:动态规划,偷不偷这个房间呢?| LeetCode:198.打家劫舍_哔哩哔哩_bilibili

代码随想录

代码:

class Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 1) return nums[0];// dp数组定义及初始化vector<int> dp(nums.size(),0); // 考虑第0~i个房间,所能偷得的最大金额为dp[i]dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);// dp数组的递推公式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数组的定义:考虑第0~i个房间,所能偷得的最大利润是dp[i]

dp数组的递推公式:有两种情况,一个是决定偷第i个房间,即dp[i - 2] + nums[i];一个是不偷第i个房间,即dp[i - 1]。dp[i] = max(dp[i-2] + nums[i],dp[i - 1])

dp数组的初始化:因为递推公式里出现了i-2,所以我们要把dp[0]和dp[1]都定义了。dp[0],只有一个房间,肯定要偷。dp[1]可以选择金额较大的房间号来偷

dp数组的遍历顺序:后面的元素依赖前面元素的取值,正序遍历。

注意:我背包问题写顺手了,最后直接数组访问越界了。应该是dp[nums.size() - 1]

2.打家劫舍2

视频讲解:动态规划,房间连成环了那还偷不偷呢?| LeetCode:213.打家劫舍II_哔哩哔哩_bilibili

代码随想录

代码:

class Solution {
public:int robRange(int start,int end,vector<int>& nums){// 左闭右闭if(start == end) return nums[start];// 定义dp数组及初始化vector<int> dp(nums.size(),0);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];}int rob(vector<int>& nums) {if(nums.size() == 1) return nums[0];return max(robRange(0,nums.size() - 2,nums),robRange(1,nums.size() - 1,nums));}
};

 思路:

        成环以后,首位元素就有了互斥的关系。所以,我们只要在上一题的基础上人为的表达这种互斥的关系即可。也就是我们可以分两步:不考虑首部元素,不考虑尾部元素。在这两种情况下,去取获得的金额最大的值来作为我们的返回结果。

        其它的情况和上一题一样,就不写了。

注意:在定义dp数组的时候,为了不用在额外地去定义每次遍历其下标的映射关系。我们不如就直接将它初始化为和nums的长度一致的数组,这样也就避免了越界访问的问题。

3.打家劫舍3

视频讲解:动态规划,房间连成树了,偷不偷呢?| LeetCode:337.打家劫舍3_哔哩哔哩_bilibili

代码随想录

代码:

class Solution {
public:unordered_map<TreeNode*,int> umap;int rob(TreeNode* root) {// 递归出口if(root == NULL) return 0;if(root->left == NULL && root->right == NULL) return root->val;if(umap[root]) return umap[root];// 偷父节点int val1 = root->val;// 跳过左孩子if(root->left) val1 += rob(root->left->left) + rob(root->left->right);// 跳过右孩子if(root->right) val1 += rob(root->right->left) + rob(root->right->right);// 不偷父节点int val2 = rob(root->left) + rob(root->right);umap[root] = max(val1,val2);return max(val1,val2);}
};

思路: 

遍历顺序: 变成了树形结构,且要用到左右孩子的信息,所以选择后续遍历。

哈希表:为了避免重复计算,已经计算过的值用哈希表存起来。

具体内容:虽然我们没有定义dp数组,但是基本的逻辑还是一样的。就是分别取考虑,偷当前节点和不偷当前节点两种情况。不偷:那就直接求左右孩子的最大金额之和;偷:那就跳过左后孩子,求左右孩子的孩子的最大金额之和。

我真的,写题完全不过脑子。。。left写错right也是没谁了。。。

这篇关于代码随想录训练营Day 50|力扣198.打家劫舍、213.打家劫舍II、337.打家劫舍III的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1033115

相关文章

动态规划---打家劫舍

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

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)