LeetCode_动态规划_中等_213.打家劫舍 II
1.题目
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下,今晚能够偷窃到的最高金额。
示例 1:
输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 3:
输入:nums = [1,2,3]
输出:3
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/house-robber-ii
2.思路
(1)动态规划
在解决本题之前,需要先了解LeetCode_动态规划_中等_198.打家劫舍这题。本题在其基础上,新增了约束条件,即第一个房屋和最后一个房屋是紧挨着的。由此我们可以分析出:首尾房间不能同时被偷窃,并且只可能有以下三种不同的情况:
① 首尾房间都不被偷窃;
② 第一间房子被偷窃,最后一间不被偷窃;
③ 最后一间房子被偷窃,第一间不被偷窃。
这三种情况中结果最大的,就是最终的答案。不过仔细分析可知,情况 ① 可选择的范围比其余的更小,那么其结果肯定最小,所以只需要比较情况 ② 和情况 ③ 即可。
相关题目:
LeetCode_动态规划_中等_198.打家劫舍
LeetCode_动态规划_递归_二叉树_中等_337.打家劫舍 III
3.代码实现(Java)
//思路1————动态规划
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
} else if (length == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
}
/*
偷窃 nums[start...end] 范围内的房屋
代码改编于【LeetCode_动态规划_中等_198.打家劫舍】
*/
public int robRange(int[] nums, int start, int end) {
int dp0 = nums[start];
int dp1 = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = dp1;
dp1 = Math.max(dp0 + nums[i], dp1);
dp0 = temp;
}
return dp1;
}
}
相关文章
- LeetCode 303 Range Sum Query - Immutable(范围总和查询-永久不变)(*)
- LeetCode高频题70. 爬楼梯,青蛙跳台阶,暴力递归的尝试,改记忆化搜索和动态规划代码
- 198、【动态规划】leetcode ——983. 最低票价:记忆化搜索(C++版本)
- 182、【动态规划/数组】leetcode ——647. 回文子串:动态规划+双指针(C++版本)
- 176、【动态规划】leetcode ——1143. 最长公共子序列(C++版本)
- 174、【动态规划/贪心算法/滑动窗口】leetcode ——674. 最长连续递增序列:一题多解 (C++版本)
- 171、【动态规划】leetcode ——309. 最佳买卖股票时机含冷冻期 (C++版本)
- 164、【动态规划】leetcode ——213. 打家劫舍 II:环形列表线性化(C++版本)
- 163、【动态规划】leetcode ——198. 打家劫舍(C++版本)
- 155、【动态规划】leetcode ——474. 一和零:三维数组+二维滚动数组(C++版本)
- 154、【动态规划】leetcode ——494. 目标和:回溯法+动态规划(C++版本)
- 153、【动态规划】leetcode ——1049. 最后一块石头的重量 II:滚动数组(C++版本)
- 152、【动态规划】leetcode ——416. 分割等和子集:滚动数组+二维数组(C++版本)
- 146、【动态规划】leetcode ——746. 使用最小花费爬楼梯:递归法+迭代法(C++版本)
- 130、【贪心算法/动态规划】leetcode ——122. 买卖股票的最佳时机 II(C++版本)
- 【算法/动态规划】leetcode刷题路线(持续更新)