You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
大意 ,数组中不能够同时取相邻的两个,能够得到最大和。
思路 :
当你要求n个房间时的最大财富是,就要考虑 n - 1 和 n - 2两种情况。
可以得到递推公式:
T(n) = Max(T(n - 1) , T(n -2) + nums[n])
可能会觉得,n - 1的时候,你也可以 + nums[n] , 但是那样的话,不就是等于T(n - 2) + nums[i] 最后结果还是没变的
实际上这里考虑的是 , 求 n 的时候,分上一次邻近与不邻近。
public class Solution { public int rob(int[] nums) { int len = nums.length; int pre = 0; int cur = 0; for(int i = 0 ; i < len ; i++) { int tmp = cur; cur = Math.max(pre + nums[i] , cur); pre = tmp; } return cur; } }
House Robber II
问题:
现在房屋不是在一条直线上 ,而是成一个圆圈。
分析:
就得分两种情况来考虑,一种就是包含起点,一种是一定不包含起点。
所以,就对数组中0 .... n - 2 个元素 进行HouseRobber I 中的求解,求得n - 2时的值
然后,再对1 .... n - 1 houseRobber I , 求的n - 1时的值,再与 n -2 比较, 就求的max.
但是这个地方可能会觉的,n - 2时的值,可能也没有包含nums[0] , 那么这时候也可以与
nums[n -1]相加啊?
---- 如果 n - 2 的没有包括nums[ 0] , 那么 n - 2 不就等于 1... n - 1中的n - 2吗?
综上,0 ..... n - 2 : 包括所有从起点开始的max
1....... n - 1 :一定不包括从起点开始的max.
public class Solution { public int rob(int[] nums) { int len = nums.length; if(len == 0) return 0; if(len == 1) return nums[0]; int startOne = robHouseInNoCircle(nums , 0 , len - 2); int startTwo = robHouseInNoCircle(nums, 1 , len - 1); return Math.max(startOne , startTwo); } int robHouseInNoCircle(int[] nums , int low , int high) { int cur = 0; int pre = 0; for(int i = low ; i <= high ; i++ ) { int tmp = cur; cur = Math.max(pre + nums[i] , cur); pre = tmp; } return cur; } }
相关推荐
HouseRobber-问题-LeetCode- @Faizansayeed28 代码 /** * 问题陈述- 你是一名职业劫匪,计划抢劫街道上的房屋。 每个房子都有一定数量的钱 藏起来,阻止你抢劫他们的唯一限制是相邻的房子有安全系统 连接,如果同一...
在这个场景中,"Roberry_house_dynamicprogramming_源码" 提到的是一个关于房屋盗窃问题的动态规划解决方案,通常被称为“House Robber”问题。这个问题源于LeetCode等在线编程挑战平台,旨在锻炼程序员的逻辑思维和...
在本题中,我们讨论了两个经典的动态规划问题,分别是“House Robber II”(#213)和“Triangle”(#120)。这两个问题都涉及到寻找最优策略,通过迭代计算求解。 1. **House Robber II**: 这个问题是“House ...
标题 "house_robber_family_problems" 暗示我们正在处理一个与计算机科学和编程相关的挑战,可能是算法问题或编程竞赛的题目。这个题目可能源自经典的“打家劫舍”(House Robber)系列问题,这是一个在算法设计中...
python python_leetcode题解之198_House_Robber.py
c c语言_leetcode题解之0337_house_robber_iii
python python_leetcode题解之213_House_Robber_II.py
本压缩包中的内容是针对LeetCode平台上的第198题“打家劫舍”(House Robber)的Python解决方案。 “打家劫舍”是一道经典的动态规划问题,其核心在于寻找最优策略,即在不触动相邻房屋的情况下,最大化抢劫的财富...
在LeetCode平台上,第337题“打家劫舍III”(House Robber III)是一道涉及深度优先搜索(DFS)和树结构的经典算法题。这道题目要求我们通过Python编程来解决一个树形结构下的抢劫问题,旨在考察我们对递归、树遍历...
本题解将深入探讨第198题“打家劫舍”(House Robber),这是一个典型的动态规划问题,对于理解该算法模式及其应用至关重要。 动态规划是一种解决最优化问题的方法,通过将大问题分解为更小的子问题来求解。在这个...
1. LeetCode 198:House Robber(打家劫舍) - 这是一个经典的动态规划问题,目标是确定在一个房子列表中,不相邻的房子可以被抢劫的最大金额。需要提交代码并附上运行结果截图。 2. LeetCode 349:Intersection ...
例如,"Unique Paths"(不同路径)和"House Robber"(打家劫舍)都是经典的动态规划题目。 3. **回溯与深度优先搜索**:这类算法通常用于解决组合优化问题和图遍历问题。例如,"N-Queens"(八皇后问题)和"Word ...
18. **House Robber**:打劫问题。这是动态规划的应用,计算在不触动相邻房屋的情况下能偷窃的最大价值。 19. **Palindrome Linked List** 和 **Palindrome Number**:判断链表或数字是否为回文。链表可以用双指针...
- **HouseRobber(打家劫舍)**:在不相邻的前提下选择最大价值。 - **LongestIncreasingContinuousSubsequence(最长递增连续子序列)**:动态规划和贪心算法均可以解决。 - **CoinsinaLine(石子游戏)**:涉及...
leetcode 和 oj OJ_Solution Solutions for OJ such as leetcode, poj and so on 版本 修改日期 修改人 1 2015-04-16 skymoney ==== ...java/houserobber https://leetcode.com/problems/house-robber/
lru cache leetcode LeetCode copy and think 加油学习 1. 时间轴 时间 题目 描述 知识点 ...House Robber 动态规划 如何确定子问题 20200525 20200525 20200525 20200525 20200525 20200525 $1 234
House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. Palindromic Substrings [647]9. Maximum Length of Pair Chain [646]10. Integer Break [343]11. Count Numbers with Unique ...
lru cache leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 ...House Robber 213 打家劫舍Ⅱ
198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 (Lintcode)92.Backpack, (Lintcode)125.Backpack II, (Lintcode)564.Backpack VI 不适用 53....