LeetCode 打家劫舍系列

点击去我的博客看看吧>-<

欢迎指正

参考来源： labuladong的算法小抄

墙裂推荐上面那个大佬的算法文章。

198. 打家劫舍

1. 解法一：自顶向下递归

有重叠子问题，所以可以选择一个备忘录

class Solution {
    private int[] memo;
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        // 从第 0 间开始抢劫
        return rob(nums, 0);
    }
    private int rob(int[] nums, int start) {
        if (start >= nums.length) return 0;
        // 说明之前计算过
        if (memo[start] != -1) return memo[start];
        int res = Math.max(
            	// 不抢这一间，就从 start + 1开始抢 
                rob(nums, start + 1),
            	// 抢了这一间，金额就是这一间的钱加上下下间之后可以抢到的钱
                nums[start] + rob(nums, start + 2)
        );
        memo[start] = res;
        return res;
    }
}

2. 解法二：自底向上动态规划

为什么是自底向上呢？我们可以这样考虑：题目要求的是从第 0 间开始抢，那么我们就先考虑从最后一间抢，然后依次往上递推

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        // 因为考虑最后一间房时，考虑 i - 1   ——> (i - 1) + 2 就是下下间房
        // dp[i] = x 表示：
    	// 从第 i 间房子开始抢劫，最多能抢到的钱为 x
    	// base case: dp[n] = 0
        int[] dp = new int[n + 2];
        for (int i = n - 1;i >= 0;i --) {
            dp[i] = Math.max(
                	// 抢下一间
                    dp[i + 1],
                	// 抢这一间和下下间
                    nums[i] + dp[i + 2]
            );
        }
        // 题目要求的就是：从第 0 间房子开始抢劫，最多能抢到的钱就是 dp[0]
        return dp[0];
    }
}

3. 优化解法二空间复杂度

我们看到，解法二中，状态转移方程之间只有相邻的两个有联系，所以考虑使用两个变量来记录状态值

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        // 记录 dp[i + 1] , dp[i + 2]
        int dp_i_1 = 0, dp_i_2 = 0;
        // 记录 dp[i]
        int dp_i = 0;
        for (int i = n - 1;i >= 0;i --) {
            dp_i = Math.max( dp_i_1, nums[i] + dp_i_2);
            // 状态的更新：相当于整体往左移动
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
}

213. 打家劫舍 II

1. 解法一：动态规划

根据题目要求，我们可以得知，抢劫只能发生在三种情况下：

1. 抢 [1, n - 2]：即头尾都不抢
2. 抢 [0, n - 2]：不抢尾
3. 抢 [1, n - 1]：不抢头

因为金额都是大于 0，所以情况 1 显然不会由于 2，3。所以我们只考虑2,3两种情况。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        // 提前排除，避免 n - 2 越界
        if (n == 1) return nums[0];
        return Math.max(
            // 抢第 [0, n - 2], 最后一间不抢
            robRange(nums, 0, n - 2),
            // 抢第 [1, n - 1], 第 1 间不抢
            robRange(nums, 1, n - 1)
        );
    }
    // 抢劫范围 [start, end]
    private int robRange(int[] nums, int start, int end) {
        int n = nums.length;
        int[] dp = new int[n + 2];
        for (int i = end;i >= start;i --) {
            dp[i] = Math.max(
                    dp[i + 1],
                    nums[i] + dp[i + 2]
            );
        }
        return dp[start];
    }
}

2. 优化解法一空间复杂度

与 198 相同，采用变量来记录状态值，然后更新变量

// rob 函数部分相同，稍微修改一下 robRange 函数
// 其实与 198 的优化一样，只是加了边界条件
private int robRange(int[] nums, int start, int end) {
    int n = nums.length;
    int dp_i_1 = 0, dp_i_2 = 0;
    int dp_i = 0;
    for (int i = end;i >= start;i --) {
        dp_i = Math.max( dp_i_1, nums[i] + dp_i_2 );
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
}

337. 打家劫舍 III

1. 解法一：带备忘录的递归

class Solution {
    // 使用 HashMap 充当备忘录， 当前节点 ——> 抢当前节点能获得的最大值
    private HashMap<TreeNode,Integer> memo = new HashMap<>();
    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root))
            return memo.get(root);
        // 抢这一间房子
        int rob_this = root.val 
            	// 抢了这间房子，那么他的左右孩子就不能抢了，需要去抢孙子节点
            	// 同时要是儿子节点为空了，直接返回 0 即可
                + (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 no_rob_this = rob(root.left) + rob(root.right);
	    // 获得两种情况下的最大值
        int res = Math.max(rob_this, no_rob_this);
        // 将当前节点与最大值的映射记入备忘录
        memo.put(root, res);
        return res;
    }
}

2. 解法二（原文章中参考的解法）：

class Solution {
    public int rob(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }
	/* 返回一个大小为 2 的数组 arr
    arr[0] 表示不抢 root 的话，得到的最大钱数
    arr[1] 表示抢 root 的话，得到的最大钱数 */
    private int[] dp(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = dp(root.left);
        int[] right = dp(root.right);
	    // 抢，下家就不能抢了
        int rob = root.val + left[0] + right[0];
        // 不抢，下家可抢可不抢，取决于收益大小
        int no_rob = Math.max(left[0], left[1]) 
                   + Math.max(right[0], right[1]);
        // 这个地方要注意返回的顺序，因为 0 位置代表不抢，1 位置代表抢，不要写反了
        return new int[]{no_rob, rob};
    }
}