109.打家劫舍
题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 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 。
思路
假设你走到第 i 间房：
- 如果你偷第 i 间，那第 i-1 间一定不能偷 所以你能拿到的是：第 i-2 间的最好金额 + 当前房间的钱
-
如果你不偷第 i 间，那你就直接继承：第 i-1 间的最好金额 所以答案就是：
-
max(偷当前, 不偷当前)
也就是：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
举个例子 [1, 2, 3, 1] - 第 1 间：只能偷 1 - 第 2 间：max(1, 2) = 2 - 第 3 间： - 偷第 3 间 = 1 + 3 = 4 - 不偷第 3 间 = 2 - 所以是 4 - 第 4 间： - 偷第 4 间 = 2 + 1 = 3 - 不偷第 4 间 = 4 - 所以是 4 最后答案是 4
用这个规律，你根本不用记整个本子
你只需要记住两个数字： - prev1：上一间房子的最好成绩 - prev2：上上间房子的最好成绩 每到一个新房子：
当前最好成绩 = max(prev1, prev2 + 当前房子的钱)
然后更新：
prev2 = prev1
prev1 = 当前最好成绩
代码实现:
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int prev2 = nums[0]; // 第1间的最好成绩
int prev1 = Math.max(nums[0], nums[1]); // 第2间的最好成绩
for (int i = 2; i < nums.length; i++) {
int cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1; // 最后一间的最好成绩
}
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!