198. 打家劫舍

• DP状态：dp[i]表示偷前i+1家的最大数目；
• DP转移方程：dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);

public int rob(int[] nums) {
    // 空间优化
    int m = 0, n = nums[0];
    for (int i = 1; i < nums.length; i++) {
        // 计算当前偷与不偷的最优解
        int dp = Math.max(m + nums[i], n);
        m = n;
        n = dp;
    }
    return n;
}

213. 打家劫舍 II

public int rob(int[] nums) {
    if (nums.length == 1) {
        return nums[0];
    }
    // 首尾相邻，偷首不能偷尾，取最优解
    return Math.max(
            rob(nums, 0, nums.length - 2),
            rob(nums, 1, nums.length - 1)
    );
}

public int rob(int[] nums, int start, int end) {
    int m = 0, n = nums[start];
    for (int i = start + 1; i <= end; i++) {
        int dp = Math.max(m + nums[i], n);
        m = n;
        n = dp;
    }
    return n;
}

337. 打家劫舍 III

DP状态比较难想，表示为当前节点的两个分支，偷与不偷。

public int rob(TreeNode root) {
    int[] arr = dfs(root);
    // 0偷 1不偷
    return Math.max(arr[0], arr[1]);
}

private int[] dfs(TreeNode node) {
    if (node == null) {
        return new int[]{0, 0};
    }
    int[] left = dfs(node.left);
    int[] right = dfs(node.right);
    return new int[]{
            // 偷当前节点，那么左右子节点不能偷
            node.val + left[1] + right[1],
            // 不偷的话，取左右子节点最优解之和
            Math.max(left[0], left[1]) + Math.max(right[0], right[1])
    };
}