打家劫舍I
1.题目
2.思路
要解决这个问题，我们可以使用动态规划的方法。我们将问题分为两个子问题：偷窃前n-1家或者偷窃前n-2家。如果我们选择偷窃第n家，那么我们就不能偷窃第n-1家，因为它们是相邻的。所以，我们可以得到如下的递推关系：
令dp[i]表示偷窃前i家能够得到的最高金额，则
- 如果我们不偷窃第i家，那么dp[i] = dp[i-1]；
- 如果我们偷窃第i家，那么dp[i] = dp[i-2] + nums[i]，其中nums[i]表示第i家房屋的金额。
最终的答案就是dp[n-1]和dp[n-2]中的较大值，因为我们可以选择偷窃最后一家或者不偷窃最后一家。
3.代码
public class 打家劫舍 {//令dp[i]表示偷窃前i家能够得到的最高金额，则//如果我们不偷窃第i家，那么dp[i]=dp[i-1]//如果我们偷窃第i家，那么dp[i]=dp[i-2]+nums[i],nums[i]表示第i家房屋的金额//最终答案就是dp[n-1],dp[n-2]中的较大值public int rob(int[] nums) {if(nums==null||nums.length==0) {return 0;}if(nums.length==1) {return nums[0];}if(nums.length==2) {return Math.max(nums[0], nums[1]);}int prev2=nums[0];int prev1=Math.max(nums[0], nums[1]);for(int i=2;i<nums.length;i++) {int curr = Math.max(prev1, prev2+nums[i]);prev2=prev1;prev1=curr;}return prev1;}public static void main(String[] args) {打家劫舍 robber = new 打家劫舍();int [] nums= {1,2,3,1};System.out.println(robber.rob(nums));}
}4.知识
1）令dp[i]表示偷窃前i家能够得到的最高金额，则
如果我们不偷窃第i家，那么dp[i]=dp[i-1]
如果我们偷窃第i家，那么dp[i]=dp[i-2]+nums[i],nums[i]表示第i家房屋的金额
最终答案就是dp[n-1],dp[n-2]中的较大值
2）代码重点：
int prev2=nums[0];
int prev1=Math.max(nums[0], nums[1]);
for(int i=2;i<nums.length;i++) {
int curr = Math.max(prev1, prev2+nums[i]);
prev2=prev1;
prev1=curr;
}
return prev1;
我们使用了两个变量prev2和prev1来存储前两个房屋的最大偷窃金额，然后遍历数组中的每个房屋，更新这两个变量的值。最后返回prev1，它代表偷窃前n-1家房屋的最大金额。
3） if(nums==null||nums.length==0) {
return 0;
}
先判断数组的是否为空或者长度为零
if(nums.length==1) {
return nums[0];
}
若数组长度为1，直接返回第一个元素的大小
if(nums.length==2) {
return Math.max(nums[0], nums[1]);
}
若数组长度为2，比较两个元素，返回较大的那个元素的值
打家劫舍II
1.题目
2.思路
与上面的“打家劫舍I”唯一的不同就是：房屋围成一圈。
为了解决这个问题，我们可以将问题分为两个子问题来解决：
- 偷窃从第一个房屋到倒数第二个房屋的最大金额（即排除最后一个房屋）。
- 偷窃从第二个房屋到最后一个房屋的最大金额（即排除第一个房屋）。
然后，取这两个子问题的解中的较大值作为最终的结果。
3.代码
package 动态规划; public class 打家劫舍II { public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; if (nums.length == 2) return Math.max(nums[0], nums[1]); int n = nums.length; // dp[i][0] 表示偷窃前 i 个房屋（不包括第 i 个房屋）时的最大金额 // dp[i][1] 表示偷窃前 i 个房屋（包括第 i 个房屋）时的最大金额 int[][] dp = new int[n][2]; dp[0][0] = 0; dp[0][1] = nums[0]; dp[1][0] = nums[0]; dp[1][1] = Math.max(nums[0], nums[1]); for (int i = 2; i < n - 1; i++) { // 不偷窃第 i 个房屋时，最大金额是前 i-1 个房屋的最大金额 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]); // 偷窃第 i 个房屋时，最大金额是前 i-2 个房屋的最大金额加上第 i 个房屋的金额 dp[i][1] = dp[i - 1][0] + nums[i]; } // 对于最后一个房屋，我们不能偷窃它，因为房屋是排列成一个圈的 // 所以我们返回偷窃前 n-1 个房屋的最大金额 return Math.max(dp[n - 2][0], dp[n - 2][1]); } public static void main(String[] args) { 打家劫舍II solution = new 打家劫舍II(); int[] nums = {2, 3, 2}; System.out.println( solution.rob(nums)); }
}4.知识
1） int n = nums.length;
// dp[i][0] 表示偷窃前 i 个房屋（不包括第 i 个房屋）时的最大金额
// dp[i][1] 表示偷窃前 i 个房屋（包括第 i 个房屋）时的最大金额
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = nums[0];
dp[1][0] = nums[0];
dp[1][1] = Math.max(nums[0], nums[1]);
既然该题用二维数组的方式解，就不能只写 dp[0][0]和dp[0][1]，会出错
2） for (int i = 2; i < n - 1; i++) {
// 不偷窃第 i 个房屋时，最大金额是前 i-1 个房屋的最大金额
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
// 偷窃第 i 个房屋时，最大金额是前 i-2 个房屋的最大金额加上第 i 个房屋的金额
dp[i][1] = dp[i - 1][0] + nums[i];
}
