Day47 打家劫舍123

2024-05-24 17:12
文章标签 123 打家劫舍 day47

本文主要是介绍Day47 打家劫舍123,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

198 打家劫舍

题目链接:198.打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
class Solution {
public:int rob(vector<int>& nums) {int len = nums.size();if(len == 1) return nums[0];vector<vector<int>> dp(len, vector<int>(2,0));//0 没偷 1 偷了dp[0][0] = 0;dp[0][1] = nums[0];for(int i = 1; i < len; i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);dp[i][1] = dp[i - 1][0] + nums[i];}return max(dp[len - 1][0], dp[len - 1][1]);}
};

本题也可以使用一维dp

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;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 打家劫舍Ⅱ

题目链接:213.打家劫舍Ⅱ

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

思路:第一个房屋和最后一个房屋,最多只有一个会被偷,因此分两种情况,分别考虑进去第一个房屋和最后一个房屋即可。

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

337 打家劫舍Ⅲ

题目链接:337.打家劫舍

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。

除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

思路:
本题是树状dp,较难,建议学习代码随想录的讲解。

class Solution {
public:// 长度为2的数组,0:不偷,1:偷vector<int> robTree(TreeNode* cur){if (cur == NULL) 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]);}
};

这篇关于Day47 打家劫舍123的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

动态规划---打家劫舍

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

RC4加密解密算法123

RC4是一种对称密码算法,它属于对称密码算法中的序列密码(streamcipher,也称为流密码),它是可变密钥长度,面向字节操作的流密码。 RC4是流密码streamcipher中的一种,为序列密码。RC4加密算法是Ron Rivest在1987年设计出的密钥长度可变的加密算法簇。起初该算法是商业机密,直到1994年,它才公诸于众。由于RC4具有算法简单,运算速度快,软硬件实现都

每日一题,力扣leetcode Hot100之198.打家劫舍

这一道题乍一看可以双层循环暴力解,但是仔细一想有可能最大利益并不是一家隔着一家偷,我可以间隔很多家偷,所以 这个题的思路还是有点像爬楼梯,用动态规划解。 首先确立动态规划的初始条件: 1.dp[0]=nums[0]只有一家 2.dp[1]=max(nums[0],nums[1])有两家选一家多的 然后确立动态规划的循环条件: dp[i]应该是什么 1.第i家能拿,那么dp[i]=n

lua 123.lua出错

http://www.cnblogs.com/whiteyun/category/203591.html --- 推荐CSDN

LeetCode讲解篇之213. 打家劫舍 II

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

第123期 | 其他随机型存储模型

通过上期学习,大家已经了解了单周期的随机型存储模型,包括需求是离散随机变量的模型六以及需求是连续的随机变量的模型七。 那么本期小编将为大家介绍其他随机型存储模型,包括需求r为连续随机变量的(s,S)存储策略的模型八和需求r为离散随机变量的(s,S)存储策略的模型九。 引言 货物单位成本为k、单位存储费为C1、单位缺货费为C2、每次订购费为C3、期初存储为I。需求r的概率分布已知

The last packet successfully received from the server was 123,051 milliseconds ago. The last packet

博客写的略水,所以提前把问题和解决问题的方式写在前面,遇到这个问题,首先分析下: 项目是不是多个数据源,事务配置是不是有问题。 查了百度,发现遇到这个问题的情况也不少,各种各样。 所以记录一下我遇到的问题和我解决的方式,望能给别人一点启发。 问题描述: 本地环境、测试服务器环境,应用启动,完全没有问题。 然后在一个镜像生产的数据库服务上启动(这个应用真是考验我的解决问题能力,也可能我的能

代码随想录训练营 Day41打卡 动态规划 part08 121. 买卖股票的最佳时机 122. 买卖股票的最佳时机II 123. 买卖股票的最佳时机III

代码随想录训练营 Day41打卡 动态规划 part08 一、力扣121. 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0

leetcode198打家劫舍

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

代码随想录Day39:198.打家劫舍、213.打家劫舍II、337.打家劫舍III

198. 打家劫舍 题目链接:LeetCode198.打家劫舍 文档讲解:代码随想录LeetCode198.打家劫舍 题解 dp[i]偷或不偷,取决于dp[i-1]和dp[i-2]是否偷 class Solution {public:int rob(vector<int>& nums) {if (nums.size() == 1)return nums[0];vector<i