概要
打家劫舍系列一共有三个题目，算是比较经典的dp的题目，我去年做过一遍今年在刷每日一题的时候又重新回顾一下这三个题目，对我的帮助还是收益满多的，话不多说先看题目。
打家劫舍1
题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例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 。
解法1
这个题目的一个最重要的特点就是相邻的两个区域不能同时选择，所以，我们可以设置一个dp数组用来保存第i个房间被偷的时候能偷到的最大金额，我们就可以写出状态方程
dp[i] = max(dp[i-1]-num[i-1], dp[i-2]) + num[i];
然后利用这个公式，我们选择dp数组中最大的一个数就是我们能偷到的最大的数。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
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 [] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] =nums[1];
int max = Math.max(dp[0],dp[1]);
for(int i=2; i<nums.length;++i){
dp[i] = Math.max(dp[i-1]-nums[i-1],dp[i-2]) + nums[i];
max = Math.max(dp[i],max);
}
return max;
}
}
|
时间复杂度和空间复杂度都是O(N)
解法2
解法1虽然能够解决问题，但是方法不够简洁，不能够一次性解决问题，还需要对dp数组中寻找一个最大的数值。
我们可以换一种思路，将dp数组表示成当偷到第i个房间的时候，所能够获得的最大金额，这个表示和解法1还是有区别的，解法1是表示第i个房间必须被偷，而这个表示方法第i个房间不一定被偷。
按照这个思路来说，当我们偷第i个房间的时候，就有两种状态，第一种状态是第i-1个房间被偷了，那么根据相邻不可同时偷取的特性，第i个房间就必须跳过，此时有dp[i] = dp[i-1],第二种个状态是第i-1个房间没有被偷，此时第i个房间就可以选择偷也可以选择不偷，此时dp[i] = dp[i-2]+nums[i];结合上面两种状态，我们可以得出：dp[i]=max(dp[i−2]+nums[i],dp[i−1])
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}
|
时间复杂度和空间复杂度都是O(N)
解法3
我们可以对方法2进行优化，因为我们看到dp[i]只和dp[i-1],dp[i-2]有关，我们可以利用这个特性，将dp数组转化为3个int整数，这也是滚动pd。代码如下：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
|
打家劫舍2
题目
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例1
输入:[2,3,2]
输出:3
解释:
你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例2
输入:[1,2,3,1]
输出:4
解释:
你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
解法1
这个题目相比较上一个题目有一个难度的提升，从单链变成了循环，这样就需要保证第一个和最后一个不能同时被偷，这样我们可以遍历两次房间，第一次遍历从头开始遍历，遍历到除了最后一个房间的所有房间。第二次从尾巴开始遍历，遍历到除了第一个房间的所有房间。方式还是和第一题的解法1一样：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
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]);
if(nums.length ==3) return Math.max(nums[0], nums[1]);
int [] dp1 = new int[nums.length];
int [] dp2 = new int[nums.length];
dp1[0] = nums[0];
dp1[1] = nums[1];
int max = Math.max(dp1[0],dp1[1]);
for(int i=2; i<nums.length-1; ++i){
dp1[i] = Math.max(dp1[i-1]-nums[i-1], dp1[i-2]) + nums[i];
max = Math.max(dp1[i], max);
}
dp2[nums.length-1 ] = nums[nums.length-1];
dp2[nums.length-2 ] = nums[nums.length-2];
max = Math.max(dp2[nums.length-1 ], max);
max = Math.max(dp2[nums.length-2 ], max);
for(int i=nums.length-3; i>=1; i--){
dp2[i] = Math.max(dp2[i+1]-nums[i+1], dp2[i+2]) + nums[i];
max = Math.max(dp2[i], max);
}
return max;
}
}
|
解法2
方式仍然是两次遍历，但是我们对dp的表达方式转化为和上一题的解法2一样。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public int rob(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
myRob(Arrays.copyOfRange(nums, 1, nums.length)));
}
private int myRob(int[] nums) {
int pre = 0, cur = 0, tmp;
for(int num : nums) {
tmp = cur;
cur = Math.max(pre + num, cur);
pre = tmp;
}
return cur;
}
}
|
打家劫舍3
题目
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例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.
解法1
第三题相对与上一题有时一个提升，是将树和dp算法结合到了一起，通常这样的关于树的dp算法，我们可以用dfs来解决。
对于树中的每个节点我们可以存储他的两个状态，一个状态是这个房间被偷的情况下，它的左右两个节点一定没有被偷，以这个房间为根节点的树所获取的最大金额，那么这个状态的最大金额selected = left.notSelected+ right.notSelected+ root.val;
第二个状态是这个房间没有被偷的情况，那么他的左右两个节点可能被偷了，也可能没有被偷。那么没有被偷的这个状态可以被表示为：notSelected = Math.max(left.selected,ledt.notSelected)+ Math.max(right.selected, right.notSelected);
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public int rob(TreeNode root) {
if(root == null) return 0;
int []rootState = dfs(root);
return Math.max(rootState[0], rootState[1]);
}
public int[] dfs(TreeNode node){
if(node == null) return new int[]{0,0};
int [] l = dfs(node.left);
int [] r = dfs(node.right);
int selected = node.val + l[1] + r[1];
int notSelected =Math.max(l[0],l[1])+ Math.max(r[0], r[1]);
return new int[]{selected,notSelected};
}
}
|