打家劫舍问题

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

// 备忘录
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;
}

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

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之前的子问题已经用不到了，所以，我们可以只使用https://qimok.cn两个变量来保存两个子问题的结果，来计算出所有的子问题。

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;
}

本题有三种情况（由于房子中的钱数都是非负数，故选择的余地大，最七墨博客优决策结果肯定不会小）：

• 第一间房子和最后一间房子都不偷 ❌
• 第一间房子偷、最后一间房子不偷 ✅
• 第一间房子不偷、最后一张房子偷 ✅

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;
}

// 备忘录
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;
}

使用一个大小为 2 的数组来表示int[] res = new int[2]（0 代表不偷，1 代表偷）
任何一个节点能https://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};
}