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 。
解题思路
动态规划的几种数组不同定义方式
int[][] dp=new int[n][2];//在第i间屋子不抢就是dp[i][0],抢就是dp[i][1];
int[] dp=new int[n+2];//n+2是为了计算最后一个n-1的情况//dp[i]表示从i坐标开始可以截获的最大钱财
第三种方式可以优化，直接记录i+1和i+2的情况
class Solution {
public int rob1(int[] nums) {
int n=nums.length;
int[][] dp=new int[n][2];
//在第i间屋子不抢就是dp[i][0],抢就是dp[i][1];
if(n==0) return 0;
dp[0][0]=0;
dp[0][1]=nums[0];
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[i];//抢就之前只能不抢
}
return Math.max(dp[n-1][0],dp[n-1][1]);
}
public int rob2(int[] nums) {
int n=nums.length;
if(n==0) return 0;
int[] dp=new int[n+2];//n+2是为了计算最后一个n-1的情况
//dp[i]表示从i坐标开始可以截获的最大钱财
//dp[n]=0:最后一个房屋对应第n-1
for(int i=n-1;i>=0;i--){
dp[i]=Math.max(dp[i+1],dp[i+2]+nums[i]);
//抢了就是间隔一个之后的钱财，不抢就是下一个之后的
}
return dp[0];
}
//优化
public int rob(int[] nums){
int n=nums.length;
if(n==1) return nums[0];
int dp_i1=0,dp_i2=0;//记录dp[i+1],dp[i+2]
int dp_i=0;//记录dp[i],最后的dp[0]就是答案
for(int i=n-1;i>=0;i--){
dp_i=Math.max(dp_i1,dp_i2+nums[i]);
dp_i2=dp_i1;
dp_i1=dp_i;
}
return dp_i;
}
}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 = [0]
输出：0
解题思路
相比于数组，该题限制了头尾的关系
对应三种情况：头尾都不抢，头尾抢头，头尾抢尾（第一种情况肯定没有后两者大--因为头尾都不抢选择更少，可以直接比较后两者）
class Solution {
public int rob(int[] nums) {
int n=nums.length;
if(n==1) return nums[0];
//该题对应三种情况：头尾都不抢，头尾抢头，头尾抢尾（第一种情况肯定没有后两者大，可以直接比较后两者）
return Math.max(rob_help(nums,0,n-2),rob_help(nums,1,n-1));
}
public int rob_help(int[] nums,int start,int end){
int dp_i1=0,dp_i2=0;
int dp_i=0;
for(int i=end;i>=start;i--){
dp_i=Math.max(dp_i1,nums[i]+dp_i2);
dp_i2=dp_i1;
dp_i1=dp_i;
}
return dp_i;
}
}- 打家劫舍 III
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
解题思路--利用递归
输入root，返回一个int[2]数组，res[0]表示不抢该root，res[1]表示抢该root
那么抢root，则证明不抢左右节点（为空则结束，不为空则抢左右节点的孩子节点）
不抢root，则可以根据利益来确定是否抢左右节点
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res=dp(root);
return Math.max(res[0],res[1]);
}
//返回一个int[2]数组，res[0]表示不抢该root，res[1]表示抢该root
public int[] dp(TreeNode root){
if(root == null) return new int[]{0,0};
int[] left=dp(root.left);
int[] right=dp(root.right);
int doit=root.val+left[0]+right[0];//root抢，在左右节点不抢
int nodoit=Math.max(left[0],left[1])+Math.max(right[0],right[1]);//root不抢，则后续可抢可不抢
return new int[]{nodoit,doit};
}
}
京公网安备 11010502036488号