打家劫舍问题
当前房屋偷与不偷取决于前一个房和前两个房是否被偷了。考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为 dp[i] 。
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 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 。
思路
当前房屋偷与不偷取决于前一个房和前两个房是否被偷了。
确定dp数组定义
dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为 dp[i] 。
确定递推公式
- 偷当前房屋：意味着前一个房不能偷，那么此时偷到的金额应为
dp[i - 2] + nums[i]； - 不偷当前房：前一间房在考虑范围内，此时偷到的金额为
dp[i - 1]。
综合上述：当然应该取两种情况的较大值，故dp[i] = Math.max(dp[i - 2] + nums[i], dp[i-1])。
初始化dp数组
从递推公式dp[i] = Math.max(dp[i - 2] + nums[i], dp[i-1])可以看出，递推公式的基础就是 dp[0] 和 dp[1] 。
从 dp[i] 的定义上来讲，dp[0] = nums[0]，dp[1] 就是 nums[0] 和 nums[1] 的最大值即：dp[1] = max(nums[0], nums[1])。
遍历顺序
由递推公式可知：dp[i] 是由 dp[i - 2] 和 dp[i - 1] 推导出来的。所以遍历顺序应该从前往后。
再加上初始化了 dp[0] 和 dp[1]，那么应为for (int i = 2; i < n; i++) .
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int rob(int[] nums) {
int n = nums.length;
if (n == 0)
return 0;
if (n == 1)
return nums[0];
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
扩展：打家劫舍 II
本题唯一的改动就是给出的房屋是首尾相连的。
为了防止首尾相邻导致的报警，可以考虑不偷尾 head 和不偷首 tail，两种情况取较大值。等于是上面代码要执行两次，那么dp数组定义不变，递推公式不变，初始化和遍历需要小改。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int rob(int[] nums) {
int n = nums.length;
if (n == 1)
return nums[0];
int head = robRange(nums, 0, n - 2);
int tail = robRange(nums, 1, n - 1);
return Math.max(head, tail);
}
private int robRange(int[] nums, int start, int end) {
if (end - start == 0)
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];
}
扩展：打家劫舍 III
题目描述
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
本题中，房屋从数组变为了二叉树，主要变化是遍历方式发生了变化。数组可以直接从下标依次访问，而二叉树不能，我们知道二叉树有前序、中序、后序三种遍历方式。在本题里，当前节点偷到的金额来自于子节点的返回值，所以当然要采用后序遍历。
解法一、暴力递归
与打家劫舍、打家劫舍 II一样，关键是要讨论当前节点抢还是不抢。
- 抢当前节点：左右孩子都不能动，但是可以考虑抢左右孩子的孩子；
- 不抢当前节点：可以考虑抢左右孩子。
1
2
3
4
5
6
7
8
9
10
public int rob(TreeNode root) {
if(root == null)
return 0;
int money = root.val;
if(root.left != null)
money += rob(root.left.left) + rob(root.left.right);
if(root.right != null)
money += rob(root.right.left) + rob(root.right.right);
return Math.max(money, rob(root.left) + rob(root.right));
}
解法二、记忆化搜索
解答一有太多重复计算，我们可以使用map记录已经计算的节点值，下次可以直接从map取，避免重复计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Map<TreeNode, Integer> map = new HashMap<>();
public int rob(TreeNode root) {
if (root == null)
return 0;
if (map.containsKey(root))
return map.get(root);
int money = root.val;
if (root.left != null)
money += rob(root.left.left) + rob(root.left.right);
if (root.right != null)
money += rob(root.right.left) + rob(root.right.right);
int res = Math.max(money, rob(root.left) + rob(root.right));
map.put(root, res);
return res;
}
解法三、树形DP
动态规划其实是使用状态转移容器来记录状态的变化。由于当前节点抢不抢所得的金额取决于子节点抢或不抢得到的金额，所以每个节点，我们都应该记录 抢 和 不抢 获得的最大金额，这就是dp数组的定义了。
dp[i]：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
后序遍历递归调用先计算出每个子节点抢和不抢的状态，然后父节点根据子节点的dp[]来计算自己的dp[]。最后结果应该为root的抢和不抢的较大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int rob(TreeNode root) {
int[] res = robAction(root);
return Math.max(res[0], res[1]);
}
private int[] robAction(TreeNode cur){
int[] dp = new int[2];
if(cur == null)
return dp;
int[] left = robAction(cur.left);
int[] right = robAction(cur.right);
// 0 不偷当前节点
dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
// 1 偷当前节点
dp[1] = cur.val + left[0] + right[0];
return dp;
}