题目描述
链接: https://leetcode-cn.com/problems/house-robber/
你是一个专业的小偷, 计划偷窃沿街的房屋, 每间房内都藏有一定的现金, 影响你偷窃的唯一限制因素是相邻的房屋装有相互连通的防盗系统. 如果两间相邻的房屋在同一晚上被小偷闯入, 系统会自动报警.
给定一个代表每个访问存放金额的非负整数数组, 计算你在不触发警报装置的情况下, 一夜之内能够偷窃到的最高金额.
示例1:
输入: [1, 2, 3, 1]
输出: 4
偷窃1号和3号. 得到1+3 = 4.
示例2:
输入: [2, 7, 9, 3, 1]
输出: 12
偷窃1号, 3号和5号. 得到2+9+1 = 12.
解题思路
由于不能偷窃两间相邻的房间, 所以在第N个房间时, 可能的情况为:
- 由于N-1个房间已经偷窃过了, 所以不能偷窃
- N-1个房间没偷, 所以当前房间可以偷.
那么在第N个房间时, 能偷到的最大金额就是这两种情况下的最大值.
转化为递推公式为:
1
|
f(n) = Max(f(n-1), f(n-2) + nums[n])
|
边界条件:
当n=0时, 表示只有一个房间, 那么最大值只能为nums[0]
当n=1时, 表示有两个房间, 我们只能偷一个, 那么f(1) = Max(nums[0] , nums[1])
DP数组实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public int rob(int[] nums) {
if (nums == null) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int[] res = new int[nums.length];
res[0] = nums[0];
res[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
res[i] = Math.max(nums[i] + res[i - 2], res[i - 1]);
}
return res[nums.length - 1];
}
|
优化
动态规划的一个优化点, 我们可以不创建数组, 而是存储中间变量, 减少空间复杂度.
这里计算n时, 只需要n-1和n-2两个值, 所以我们可以定义两个变量来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public int rob2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int x = nums[0], y = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int temp = y;
y = Math.max(nums[i] + x, y);
x = temp;
}
return y;
}
|