House Robber

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. Can not break two adjacent houses,

• Time: O(n)
• Space: O(n)

public int rob(int[] nums) {
    if (nums == null || nums.length == 0)
        return 0;
    int[] dp = new int[nums.length + 1];
    dp[0] = 0;
    dp[1] = nums[0];
    for (int i = 2; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
    }
    return dp[nums.length];
}

House Robber II

All houses at this place are arranged in a circle.

• Time: O(n)
• Space: O(n)

public int rob(int[] nums) {
    if (nums == null || nums.length == 0)
        return 0;
    int n = nums.length;
    if (n == 1) {
        return nums[0];
    }
    if (n == 2) {
        return Math.max(nums[1], nums[0]);
    }
    int[] dp1 = new int[n], dp2 = new int[n];;
    dp1[0] = 0;
    dp1[1] = nums[0];
    for (int i = 2; i < n; i++) {
        dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i - 1]);
    }
    dp2[0] = 0;
    dp2[1] = nums[1];
    for (int i = 2; i < n; i++) {
        dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
    }
    return Math.max(dp1[n - 1], dp2[n - 1]);
}