算法

打家劫舍问题

言七墨 · 9月13日 · 2020年 · 720次已读

整理于本人的学习笔记..

一、打家劫舍 I

自顶向下、使用备忘录递归解法

自顶向下:递归一般是自顶向下,依赖于子问题优化函数的结果,只有子问题完全求出,也就是子问题的递归返回结果,原问题才能求解。

// 备忘录
private int[] memo;

public int rob(int[] nums) {
    // 初始化备忘录
    memo = new int[nums.length];
    Arrays.fill(memo, -1);
    // 强盗从第 0 间房子开始偷窃
    return dp(nums, 0);
}

// 返回 dp[start..] 能偷到的最大值
private int dp(int[] nums, int start) {
    if (start >= nums.length) {
        return 0;
    }
    // 避免重复计算
    if (memo[start] != -1) return memo[start];
    // 不偷,去下家 || 偷,去下下家  
    int res = Math.max(dp(nums, start + 1),  nums[start] + dp(nums, start + 2));
    // 记入备忘录
    memo[start] = res;
    return res;
}

自底向上、使用dp数组的解法

自底向上:迭代法一般是自底向上,巧妙的安排求解顺序,从最小的问题开始,自底向上求解。每次求新的问题时,它的子问题的解已经计算出来了。

public int rob(int[] nums) {
    int len = nums.length;
    if (len == 0) {
        return 0;
    }
    // 偷前..个房子的最大金额
    int[] dp = new int[len + 1];
    // base case:没有房子
    dp[0] = 0;
    // base case:只有一个房子
    dp[1] = nums[0];
    for (int i = 2; i <= len; i++) {
        // 偷前 i - 1 间房子,最后一间不偷 || 偷前 i - 2 间房子和最后一间房子  
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }
    return dp[len];
}

空间优化

通过自底向上、使用dp数组的解法,发现在计算dp[len]时,实际上只用到了dp[i - 1]dp[n - 2]n - 3之前的子问题已经用不到了,所以,我们可以只使用两个变量来保存两个子问题的结果,来计算出所有的子问题。

public int rob(int[] nums) {
    int prev = 0;
    int curr = 0;
    // 每次循环,计算“偷到当前房子为止的最大金额”
    for (int num : nums) {
        // 循环开始时,curr 代表 dp[i - 1],prev 表示 dp[i - 2]
        int temp = Math.max(curr, prev + num);
        prev = curr;
        curr = temp;
        // 循环结束时,curr 表示 dp[i],prev 表示 dp[i - 1]
    }
    return curr;
}

二、打家劫舍 II

本题有三种情况(由于房子中的钱数都是非负数,故选择的余地大,最优决策结果肯定不会小):

  • 第一间房子和最后一间七墨博客房子都不偷 ❌
  • 第一间房子偷、最后一间房子不偷 ✅
  • 第一间房子不偷、最后一张房子偷 ✅
public int rob(int[] nums) {
    int len = nums.length;
    if (len == 1) return nums[0];
    // 第一间房子偷、最后一间房子不偷 || 第一间房子不偷、最后一张房子偷
    return Math.max(robRange(nums, 0, len - 2), robRange(nums, 1, len - 1));
}
// 仅计算闭区间 [start, end] 的最优结果
private int robRange(int[] nums, int start, int end)  {
    int prev = 0, curr = 0;
    for (int i = end; i >= start; i--) {
        int temp = Math.max(curr, nums[i] + prev);
        prev = curr;
        curr = temp;
    }
    return curr;
}

三、打家劫舍 III

自顶向下、使用备忘录递归解法

// 备忘录
Map<TreeNode, Integer> memo = new HashMap<>();
public int rob(TreeNode root) {
    if (root == null) return 0;
    // 利用备忘录消除重叠子问题
    if (memo.containsKey(root)) return memo.get(root);
    // 偷,然后去下下家
    int steal = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right)) + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
    // 不偷,然后去下家
    int not_steal = rob(root.left) + rob(root.right);
    int res = Math.max(steal, not_steal);
    memo.put(root, res);
    return res;
}

终极解法

https://qimok.cn

使用一个大小为 2 的数组来表示int[] res = new int[2](0 代表不偷,1 代表偷)
任何一个节点能偷到的最大钱的状态可以定义为言七墨

  • 当前节点不偷:当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
  • 当前节点偷:当前节点的钱数 + 当前节点能偷到的最大钱数 = https://qimok.cnhttps://qimok.cn左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱
public int rob(TreeNode root) {
    int[] res = dp(root);
    return Math.max(res[0], res[1]);
}

/**
 * arr[0]:表示不偷 root 的话,得到的最大钱数
 * arr[1]:表示偷 root 的话,得到的最大钱数
 *
 * @param root
 * @return 返回一个大小为 2 的数组 arr
 */
private int[] dp(TreeNode root) {
    if (root == null) return new int[]{0, 0};
    int[] left = dp(root.left);
    int[] right = dp(root.right);
    // 偷,下家就不能偷了
    int steal = root.val + left[0] + right[0];
    // 不偷,下家可偷可不偷,取决于收益的大小
    int not_steal = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return new int[]{not_steal, steal};
}
2 条回应
  1. 匿名2020-9-25 · 23:54

    不用登陆也能评论?