打家劫舍

动态规划的题总能让人绝望,简单的几行代码,想破脑袋都想不出来😭

打家劫舍

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

思路

看了 Carl 哥的题解,豁然开朗,当前房屋偷不偷,取决于前一家或者两家偷不偷

如果偷第 i 间房间,那么 dp[i] = dp[i - 2] + nums[i],第 i - 1间不会考虑

如果不偷第i间房间,那么dp[i] = dp[i - 1],这里并不是说一定偷第i - 1房间,只是考虑

所以:dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1])

从递推公式可以看出,初始化为:dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1])

代码

class Solution {
public int rob(int[] nums) {
if(nums.length < 2){
return nums[0];
}
int dp[] = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i = 2;i < nums.length;i++){
dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);
}
return dp[nums.length - 1];
}
}

打家劫舍Ⅱ

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

思路

相比于打家劫舍Ⅰ,差别在于房间成环了,这样一来,首尾不能同时取到,所以分为两种情况,含首不含尾,含尾不含首,其实还有一种情况,就是首尾都不取,不过已经包含在这两种情况里了,因为所谓的取或不取只是考虑,并不是一定取,不取则一定没机会取

代码

class Solution {
public int rob(int[] nums) {
if(nums.length < 2){
return nums[0];
}
int withoutHead = robWithoutHeadOrTail(nums,1,nums.length - 1);
int withoutTail = robWithoutHeadOrTail(nums,0,nums.length - 2);
return Math.max(withoutHead,withoutTail);
}
public int robWithoutHeadOrTail(int[] nums,int start,int end){
if(end - start + 1 < 2) return nums[start];
int dp[] = new int[nums.length];
dp[start] = nums[start];
dp[start + 1] = Math.max(nums[start],nums[start + 1]);
for(int i = start + 2;i <= end;i++){
dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);
}
return dp[end];
}
}

可以看出,和打家劫舍Ⅰ代码基本完全一致,不过将两种情况作了比较

打家劫舍Ⅲ

题目描述

思路

每个节点还是两个状态,偷或者不偷

  • 当前节点选择偷时,那么两个孩子节点不能选择偷
  • 当前节点选择不偷时,那么两个孩子节点需要偷最多的钱

使用一个数组来表示当前节点偷或者不偷得到的最大钱数 int[] res = new int[2]

某节点可偷到的最大金额状态为:

  • 当前节点不偷:左孩子能偷到的钱 + 右孩子能偷到的钱
  • 当前节点偷:当前节点钱数 + 左孩子选择不偷自己能得到的钱数 + 右孩子选择不偷自己时能得到的钱数

递推公式就出来了:

root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])
root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;

代码

下面这个LeetCode超时了,采用的是记忆化递归,不过时间复杂度已经降到了$O(n)$

class Solution {
public int rob(TreeNode root) {
HashMap<TreeNode,Integer> map = new HashMap<>();
if(root == null) return 0;
if(root.left == null && root.right == null) return root.val;
if(map.containsKey(root)) return map.get(root);
// 偷父节点
int val1 = root.val;
if(root.left != null) val1 += rob(root.left.left) + rob(root.left.right); // 跳过root.left
if(root.right != null) val1 += rob(root.right.right) + rob(root.right.left); // 跳过root.right
// 偷父节点
int val2 = rob(root.left) + rob(root.right);
int max = Math.max(val1,val2);
map.put(root,max);
return max;
}
}

这才是最好的答案!动态规划

class Solution {
public int rob(TreeNode root) {
int[] result = robMax(root);
return Math.max(result[0],result[1]);
}
public int[] robMax(TreeNode root){
int[] result = new int[2];
if(root == null) return result;

int[] left = robMax(root.left);
int[] right = robMax(root.right);
// 当前节点不偷
result[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
// 当前节点偷
result[1] = root.val + left[0] + right[0];

return result;
}
}

总结!!!

我不相信小偷有这么厉害,能看出来房屋排成了二叉树结构,分明是程序猿下岗再就业!😖