打家劫舍
198. 打家劫舍
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
方法：动态规划
首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。
如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 $k~(k>2)$ 间房屋，有两个选项：
- 偷窃第 $k$ 间房屋，那么就不能偷窃第 $k-1$ 间房屋，偷窃总金额为前 $k-2$ 间房屋的最高总金额与第 $k$ 间房屋的金额之和。
- 不偷窃第 $k$ 间房屋，偷窃总金额为前 $k-1$ 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 $k$ 间房屋能偷窃到的最高总金额。
用 $\textit{dp}[i]$表示前 $i$ 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程： \(dp[i] = max\{ dp[i-1], dp[i-2] + nums[i] \}\) 其中边界条件： \(dp[0] = nums[0] \\ dp[1] = max\{ nums[0], nums[1] \}\) 最终答案是 $dp[length - 1]$，其中 $length$ 是数组的长度。
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
}
if (length == 2) {
return Math.max(nums[0], nums[1]);
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[1], nums[0]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[length - 1];
}
}
滚动数组优化代码
class Solution {
public int rob(int[] nums) {
/* 滚动数组优化 */
int length = nums.length;
if (length == 1) {
return nums[0];
}
int first = nums[0], second = Math.max(nums[1], nums[0]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(second, first + nums[i]);
first = temp;
}
return second;
}
}
213. 打家劫舍 II
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
实例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
方法：动态规划
环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题：
- 在不偷窃第一个房子的情况下（即 $nums[1:length-1]$），最大金额是 $p_1$；
- 在不偷窃最后一个房子的情况下（即 $nums[0:n-1]$），最大金额是 $p_2$。
- 综合偷窃最大金额： 为以上两种情况的较大值，即 $max(p1,p2)$ 。
将问题简化为两个 单排排列房间子问题后，就可以使用198. 打家劫舍的代码解决了。
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]);
} else {
return Math.max(myRob(0, length - 2, nums), myRob(1, length - 1, nums));
}
}
private int myRob(int start, int end, int[] nums) {
int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = second;
second = Math.max(second, first + nums[i]);
first = temp;
}
return second;
}
}