LeetCode198.打家劫舍

2024-03-03 09:12
文章标签 打家劫舍 leetcode198

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

题目

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

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

示例

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路

这是一个经典的动态规划问题,通常被称为 “打家劫舍” 问题。在不触动警报装置的情况下偷窃最高金额,可以使用动态规划的方法来解决。

首先考虑最简单的情况。如果只有一间房屋,则偷窃该房屋,可以偷窃到最高总金额。如果只有两间房屋,则由于两间房屋相邻,不能同时偷窃,只能偷窃其中的一间房屋,因此选择其中金额较高的房屋进行偷窃,可以偷窃到最高总金额。

如果房屋数量大于两间,应该如何计算能够偷窃到的最高总金额呢?对于第 k (k>2) 间房屋,有两个选项:

  • 偷窃第 k 间房屋,那么就不能偷窃第 k−1 间房屋,偷窃总金额为前 k−2间房屋的最高总金额与第 kkk 间房屋的金额之和。

  • 不偷窃第 k 间房屋,偷窃总金额为前 k−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项,该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。

假设 dp[i] 表示偷取前 i 个房屋能够获得的最高金额,那么状态转移方程可以定义如下:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

其中,dp[i-1] 表示不偷第 i 个房屋时能够获得的最高金额,dp[i-2] + nums[i] 表示偷取第 i 个房屋时能够获得的最高金额(因为不能偷相邻的房屋,所以要加上 i-2 位置的金额)。

Code

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if(n==1)return nums[0];vector<int>dp(n);dp[0]=nums[0];dp[1]=max(dp[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];}
};

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



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

相关文章

动态规划---打家劫舍

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

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

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

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

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

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

代码随想录算法训练营第三十九天 | 198.打家劫舍 , 213.打家劫舍II , 337.打家劫舍III

目录 198.打家劫舍 思路 1.确定dp数组(dp table)以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组 方法一: 动态规划-一维 方法二:动态规划-二维 方法三:动态规划-两个变量 213.打家劫舍II 思路 方法一:动态规划- 方法二:动态规划-二维 方法三:动态规划-不封装函数  337.打家劫舍III

day 39 代码随想录 | 打家劫舍 动态规划

198.打家劫舍 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 示例 1:输入:[1,2,3,1]输出:4 这题其实就是一个动态规划的题,经典

【代码随想录训练营第42期 Day39打卡 - 打家劫舍问题 - LeetCode 198.打家劫舍 213.打家劫舍II 337.打家劫舍III

目录 一、做题心得 二、题目与题解 题目一:198.打家劫舍 题目链接 题解:动态规划 题目二:213.打家劫舍II 题目链接 题解:动态规划  题目三:337.打家劫舍III 题目链接 题解:动态规划 三、小结 一、做题心得 今天是打家劫舍的一天,来到了动态规划章节的Part7。打家劫舍问题是动态规划算法很经典的一个应用,今天将从三道题目对其进行探讨。

代码随想录算法训练营第三十九天|198.打家劫舍、

题目链接:198. 打家劫舍 - 力扣(LeetCode) 思路:因为隔一家才能取,所以当前最大的价值要么是dp[i-2] + nums[i] 或者是 dp[i-1] class Solution(object):def rob(self, nums):""":type nums: List[int]:rtype: int"""dp = [0] * len(nums)if (len(nums)

24暑假算法刷题 | Day39 | 动态规划 VII | LeetCode 198. 打家劫舍,213. 打家劫舍 II,337. 打家劫舍 III

目录 198. 打家劫舍题目描述题解 213. 打家劫舍 II题目描述题解 337. 打家劫舍 III题目描述题解 打家劫舍的一天 😈 198. 打家劫舍 点此跳转题目链接 题目描述 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动