原题地址：
打家劫舍系列是一套经典的DP题目（打家劫舍IV除外），通过这三道题可以帮助我们由浅入深地了解到一些动态规划的核心思想
打家劫舍 I
创建一个数组dp，dp[i]表示小偷经过第i间房屋时偷取到的最大金额
当小偷经过一间房屋i时，他有两种选择：
- 偷取房间i，那么小偷此时一定是没有偷取房间i-1的，此时偷窃金额dp[i]=nums[i]+dp[i-2]
- 不偷取房间i，那么小偷无视了这间房间，相当于这间房间不存在，此时的金额dp[i]=dp[i-1]
二者取最大值，于是我们就有：
考虑到边界条件：
- 对于房间0，理所当然偷这间房比不偷要赚，dp[0]=nums[0]
- 对于房间1，小偷只能从0和1中选择一间偷取，dp[1]=max(nums[0],nums[1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int rob(int[] nums) {
if(nums.length==1)return nums[0];
int[] dp=new int[nums.length];
int max=0;
for(int i=0;i<nums.length;i++){
if(i==0)dp[i]=nums[i];
else if(i==1)dp[i]=Math.max(nums[i],nums[i-1]);
else dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
if(max<dp[i])max=dp[i];
}
return max;
}
}
|
打家劫舍 II
这道题在打家劫舍 I的基础上首尾相接，但是思路仍然是不变的
首尾相接看似麻烦，实际上只添加了一个限定条件：偷0房就不能偷n-1房，偷n-1房就不能偷0房
所以仍然按照打家劫舍 I的原则执行两次dp，第一次区间为[0——n-2]，第二次区间为[1——n-1]即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int rob(int[] nums) {
if(nums.length==1)return nums[0];
int[][] dp=new int[2][nums.length];
int max=0;
for(int i=0;i<nums.length-1;i++){
if(i==0)dp[0][i]=nums[i];
else if(i==1)dp[0][i]=Math.max(nums[i],nums[i-1]);
else dp[0][i]=Math.max(dp[0][i-2]+nums[i],dp[0][i-1]);
if(max<dp[0][i])max=dp[0][i];
}
for(int i=1;i<nums.length;i++){
if(i==1)dp[1][i]=nums[i];
else if(i==2)dp[1][i]=Math.max(nums[i],nums[i-1]);
else dp[1][i]=Math.max(dp[1][i-2]+nums[i],dp[1][i-1]);
if(max<dp[1][i])max=dp[1][i];
}
return max;
}
}
|
打家劫舍 III
有的人提到一开始想要BFS对树进行层次遍历，然后将树状DP转换为每层资金和的一维DP的错误解法，原因在于原题给出的样例是具有误导性的，小偷并不是一次偷取一层，要么一层全偷，要么一层全不偷的，更有可能是一层中的几个被偷取，另几个不被偷取，将第二个样例[3,4,5,1,3,null,1]改为[3,4,5,1,10,null,1]就是这种情况了
虽然涉及到了二叉树，但这道题仍然秉持着打家劫舍系列的核心思想：偷/不偷当前节点
对于打家劫舍I和打家劫舍II，我们永远是：
- 要么偷取当前节点i，然后再加上0——i-2之间能偷取的最大值
- 要么不偷取当前节点i，直接等于0——i-1之间能偷取的最大值
对于这道题，我们有着相似的思想，对于一个节点node，我们有类似的原则：
- 偷取当前节点i，然后再加上它的孙子们的最大值的和
- 不偷取当前节点i，然后加上它的儿子们的最大值的和
由于要先更新子节点后才能用子节点的数据来更新当前节点，所以我们需要用后序遍历的方式来遍历这棵树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int rob(TreeNode root) {
treeDP(root);
return root.val;
}
void treeDP(TreeNode node){
if(node==null)return;
treeDP(node.left);
treeDP(node.right);
int selected=node.val+
(node.left==null?0:(
(node.left.left==null?0:node.left.left.val)+
(node.left.right==null?0:node.left.right.val)))+
(node.right==null?0:(
(node.right.left==null?0:node.right.left.val)+
(node.right.right==null?0:node.right.right.val)));
int unselected=
(node.left==null?0:node.left.val)+
(node.right==null?0:node.right.val);
node.val=Math.max(selected,unselected);
}
}
|
