198. 打家劫舍
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
解题思路
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// 第 i 家的不偷/偷最高金额
int[][] dp = new int[n][2];
dp[0][1] = nums[0];
for (int i = 1; i < n; i++) {
// 不偷第 i 家, 前一家可以偷也可以不偷
dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0]);
// 偷第 i 家, 前一家一定没被偷
dp[i][1] = dp[i - 1][0] + nums[i];
}
return Math.max(dp[n - 1][0], dp[n - 1][1]);
}
}
也可以转换为一维数组，但是dp数组的含义就变为了，偷到第i家的最高金额
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
// 偷第 i 家的偷最高金额
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
}
213. 打家劫舍 II
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
解题思路
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
// 偷到第 i 家的金额
int[][] dp = new int[n][2];
dp[0][1] = nums[0];
// 偷第 1 家 => 只能偷到第 n - 1 家
for (int i = 1; i < n - 1; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + nums[i];
}
int ans1 = Math.max(dp[n - 2][0], dp[n - 2][1]);
// 不偷第 1 家 => 可以偷到第 n 家
dp[1][0] = 0; dp[1][1] = nums[1];
for (int i = 2; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + nums[i];
}
int ans2 = Math.max(dp[n - 1][0], dp[n - 1][1]);
return Math.max(ans1, ans2);
}
}
但这样的代码太丑陋了，重构一下，用一个robAction函数表示偷[start, end]这个区间的房子的结果
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
// 偷第 1 家 => 只能偷到第 n - 1 家
// 不偷第 1 家 => 可以偷到第 n 家
return Math.max(robAction(nums, 0, n - 2), robAction(nums, 1, n - 1));
}
public int robAction(int[] nums, int start, int end) {
int n = end - start;
if (n == 0) return nums[start];
int[][] dp = new int[n + 1][2];
dp[0][1] = nums[start];
for (int i = 1; i <= n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + nums[start + i];
}
return Math.max(dp[n][0], dp[n][1]);
}
}
337. 打家劫舍 III
题目描述
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
解题思路
class Solution {
public int rob(TreeNode root) {
// dp[0]: 不偷当前房子 dp[1]: 偷当前房子
int[] dp = robAction(root);
return Math.max(dp[0], dp[1]);
}
public int[] robAction(TreeNode root) {
if (root == null) {
return new int[2];
}
// 左孩子打劫结果
int[] left = robAction(root.left);
// 右孩子打劫结果
int[] right = robAction(root.right);
// 要抢当前, 左右孩子一定没被抢
int robCurentHouse = left[0] + right[0] + root.val;
// 不抢当前, 左右孩子有一个被抢、都被抢、都没抢都满足不抢当前条件, 取金额最多
int noRobCurentHouse = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{noRobCurentHouse, robCurentHouse};
}
}
评论