之前刷过剑指Offer里的动态规划题，当时感觉掌握了，但回头再做这类题的时候，还是感觉很棘手。于是又在LeetCode里刷了几道动态规划的题，希望自己的能力有所提高😋

1. 动态规划

动态规划适用于父问题的解由子问题而来。一般还用于优化递归过程(例如斐波那契数列。)

  • 状态划分
  • 状态确定
  • 状态转移
  • 确定边界

2. 题目

2.1 打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

例如：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

解法

思路：我们直接用动态规划的步骤来思考。

  • 状态划分：偷窃n个房子的最高金额划分为偷窃n-1, n-2, …个房子的最高金额得来
  • 状态确定：$dp[i]$表示$i$个房子偷取的最高金额
  • 状态转移：由于不可以偷相邻的房子，那么对于第$i$个房子来说，可以选择偷，也可以选择不偷。如果偷，那么第$i - 1$个房子就不能偷了，此时，$dp[i] = nums[i] + dp[i - 2]$; 而如果不偷，$dp[i] = dp[i - 1]$。所以最终的状态转移方程为
  • 确定边界：偷0个房子的最高金额为0

空间优化：由于转移方程只与当前的前两个值有关，所以可以不使用数组，降低空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // 用来放置i-1, i-2时的最高金额
        int first = 0, second = 0, cur = 0;
        for (int i = 0; i < nums.length; i++) {
            cur = Math.max(nums[i] + first, second);
            first = second;
            second = cur;
        }
        return cur;
    }
}

时间复杂度为$O(n)$ 遍历了nums数组
空间复杂度为$O(1)$ 几个变量使用常数大小的额外空间

2.2 打家劫舍II

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

例如：

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

解法

思路：这里比最初的题目多了一个条件——房屋围成一圈，即头部屋子和尾部屋子不能同时偷取。可以将这个数组分成两个单排数组考虑${nums[0:length-2]\ \ nums[1:length-1]}$，这样就等效于首尾两个屋子不能同时偷了，而且包含两个屋子都不偷的情况。

ps: 注意数组长度为1的情况😶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;
class Solution {
    public int rob(int[] nums) {
        if (nums == null || 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 first = 0, second = 0, cur = 0;
        for (int i = 0; i < nums.length; i++) {
            cur = Math.max(nums[i] + first, second);
            first = second;
            second = cur;
        }
        return cur;
    }
}

时间复杂度为$O(2*n)$ 遍历了两个nums数组
空间复杂度为$O(1)$ 几个变量使用常数大小的额外空间

2.3 打家劫舍III

题目描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

例如：

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

解法

思路：

  • 状态划分：当前节点的最高金额可由其子节点得来。
  • 状态确定：使用Map保存数据，$mapA(i)$表示$i$节点不偷时的最高金额，$mapB(i)$表示$i$节点偷取时的最高金额。
  • 状态转移：当不偷取$i$节点，它的左右子节点可以偷，也可以不偷，此时，$mapA(i) = max(mapA(i.left), mapB(i.left)) + max(mapA(i.right), mapB(i.right))$；偷取$i$节点时，它的左右子节点不可再偷，$mapB(i) = i.val + mapA(i.left) + map(i.right)$
  • 确定边界：叶节点的子节点的偷取金额为0。

空间优化：我们可以使用三个数组来保存当前节点及其左右子节点的最高偷取金额。

使用后序遍历来遍历树。

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
/**
 * 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) {
        if (root == null) return 0;
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        // reuslt[0]表示不偷取当前节点 result[1]表示偷取当前节点。
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int[] result = new int[2];
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = node.val + left[0] + right[0];
        return result;
    }
}

时间复杂度为$O(n)$ 遍历了整个树
空间复杂度为$O(logn)$ 递归栈的空间为树的深度

3. 参考