Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
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.
[balabala] 数组表示环后,根据题意,最后一个元素不能和第一个元素同时参与计算,为此可使用两个dp数组将题目重新简化为非环的House Robber, dp[] 用于计算0 号 房子 到 n - 2 号房子能抢到的最大金额,dp2[]用于计算 1号房子 到 n - 1号房子能抢到的最大金额,最后取两个dp数组最后元素的最大值。
// method 1 public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; int n = nums.length; if (n == 1) return nums[0]; if (n == 2) return Math.max(nums[0], nums[1]); int[] dp = new int[n - 1]; int[] dp2 = new int[n - 1]; dp[0] = nums[0]; dp[1] = Math.max(dp[0], nums[1]); dp2[0] = nums[n - 1]; dp2[1] = Math.max(dp2[0], nums[0]); for (int i = 2; i < n - 1; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } for (int i = 1; i < n - 2; i++) { dp2[i + 1] = Math.max(dp2[i - 1] + nums[i], dp2[i]); } return Math.max(dp[n - 2], dp2[n - 2]); } // method 2 // 变成环形后,第一家和最后一家不能同时取,因此分两种情况讨论, // 调用原House Robber中的方法两次, 取较大值 public int rob2(int[] nums) { if (nums == null || nums.length == 0) return 0; int n = nums.length; if (n == 1) return nums[0]; return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1)); } private int robLinear(int[] nums, int start, int end) { int[] dp = new int[end - start + 2]; int n = dp.length; dp[0] = 0; dp[1] = nums[start]; for (int i = start + 1; i <= end; i++) { int k = i - start + 1; dp[k] = Math.max(dp[k - 1], dp[k - 2] + nums[i]); } return dp[n - 1]; }
相关推荐
python python_leetcode题解之213_House_Robber_II.py
HouseRobber-问题-LeetCode- @Faizansayeed28 代码 /** * 问题陈述- 你是一名职业劫匪,计划抢劫街道上的房屋。 每个房子都有一定数量的钱 藏起来,阻止你抢劫他们的唯一限制是相邻的房子有安全系统 连接,如果同一...
c c语言_leetcode题解之0337_house_robber_iii
python python_leetcode题解之198_House_Robber.py
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 ...
2. 动态规划:"House Robber"(打家劫舍)系列问题,展示了动态规划在求解最优解方面的应用,通过状态转移方程可以求得最大收益。 3. 分治法:"Median of Two Sorted Arrays"(两个排序数组的中位数)是分治策略的...
leetcode 和 oj OJ_Solution Solutions for OJ such as leetcode, poj and so on 版本 ...https://leetcode.com/problems/two-sum/ ...java/houserobber https://leetcode.com/problems/house-robber/
1. 动态规划:如“House Robber”问题,考察了如何用动态规划状态转移方程来求解最优决策。 2. 二叉树:例如“Lowest Common Ancestor of a Binary Tree”涉及到二叉树的遍历和节点查找。 3. 图论:如“Course ...
本压缩包中的内容是针对LeetCode平台上的第198题“打家劫舍”(House Robber)的Python解决方案。 “打家劫舍”是一道经典的动态规划问题,其核心在于寻找最优策略,即在不触动相邻房屋的情况下,最大化抢劫的财富...
本题解将深入探讨第198题“打家劫舍”(House Robber),这是一个典型的动态规划问题,对于理解该算法模式及其应用至关重要。 动态规划是一种解决最优化问题的方法,通过将大问题分解为更小的子问题来求解。在这个...
lru cache leetcode LeetCode copy and think 加油学习 1. 时间轴 时间 题目 描述 知识点 ...House Robber 动态规划 如何确定子问题 20200525 20200525 20200525 20200525 20200525 20200525 $1 234
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
在LeetCode平台上,第337题“打家劫舍III”(House Robber III)是一道涉及深度优先搜索(DFS)和树结构的经典算法题。这道题目要求我们通过Python编程来解决一个树形结构下的抢劫问题,旨在考察我们对递归、树遍历...
House Robber 学会了数组的创建,以及动态规划最基本的题目 2021.2.2 322 兑换钱币 学会了 Arrays.fill 的使用,以及查看源码,返回 记录在哔哩哔哩 中 2021.2.3 53 最大子数字之和 先更新max,再将负数赋值为0 62 ...
lru cache leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 ...House Robber 213 打家劫舍Ⅱ
例如,"Unique Paths"(不同路径)和"House Robber"(打家劫舍)都是经典的动态规划题目。 3. **回溯与深度优先搜索**:这类算法通常用于解决组合优化问题和图遍历问题。例如,"N-Queens"(八皇后问题)和"Word ...
18. **House Robber**:打劫问题。这是动态规划的应用,计算在不触动相邻房屋的情况下能偷窃的最大价值。 19. **Palindrome Linked List** 和 **Palindrome Number**:判断链表或数字是否为回文。链表可以用双指针...
编码实践 编码实践 模式:二进制搜索: 二进制搜索 二进制搜索: : 排序数组的上限: : ... 众议院强盗2: ://leetcode.com/problems/house-robber-ii/discuss/59921/9-lines-0ms-O(1)-Space-C++-sol
HouseRobber(#198), ClimbingStairs(#70), CoinChange(#322), EditDistance(#72) 图 : 集合的合并(直接求并、按大小求并和按深度求并)、根搜寻(路径压缩) : 有向图和无向图的邻接表表示方法 : 图的深度优先和广度...