LeetCode 198. House Robber

, , , , , ,

Question

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

Follow-up: Can you do this in O(N) time and constant space?

Example

1
2
3
4
5
input: [2, 4, 6, 2, 5] 
return 13 (since pick 2, 6 and 5)

input: [5, 1, 1, 5]
return 10 (since pick 5 and 5)

Solution

The strategy behind this question would be do we need to choose or not with the non-adjacent limitation.

Code

Recursion

1
2
3
4
5
6
7
8
9
10
// time:O(2^n) space:O(n)
public int rob(int[] nums) {
        return helper(nums, nums.length - 1);
    }
    
    public int helper(int[] nums, int n) {
        if (n < 0) return 0;
        // rob current one or not rob.
        return Math.max(helper(nums, n - 1), helper(nums, n - 2) + nums[n]);
    }

Recursion + Memo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// time:O(n) space:O(n)
public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return helper(nums, nums.length - 1, memo);
    }
    
    public int helper(int[] nums, int n, int[] memo) {
        if (n < 0) return 0;
        if (memo[n] != -1) return memo[n];
        int rob = helper(nums, n - 2, memo) + nums[n];
        int notRob = helper(nums, n - 1, memo);
        memo[n] = Math.max(notRob, rob);
        return memo[n];
    }

Bottom Up Solution (DP)

1
2
3
4
5
6
7
8
9
10
11
12
// time:O(n) space:O(n)
public int rob(int[] nums) {
        int n = nums.length;
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            int rob = nums[i] + (i >= 2 ? dp[i - 2] : 0);
            int not = (i >= 1) ? dp[i - 1] : 0;
            dp[i] = Math.max(rob, not);
        }
        return dp[n - 1];
    }

Space O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
// time:O(n) space:O(1)
public int rob(int[] nums) {
        int n = nums.length;
        if (nums == null || nums.length == 0) return 0;
        int rob = 0;
        int not = 0;
        for (int num : nums) {
            int prevMax = Math.max(rob, not);
            rob = not + num;
            not = prevMax;
        }
        return Math.max(rob, not);
    }

​