House Robber

NeetCode: House Robber · LeetCode: 198. House Robber · Difficulty: Medium

You are robbing houses along a street. nums[i] is the money in house i. Adjacent houses have linked alarms, so you cannot rob two neighbours. Return the maximum amount you can rob.

Example

Text

Input:  nums = [1, 2, 3, 1]       Output: 4    (rob houses 0 and 2)
Input:  nums = [2, 7, 9, 3, 1]    Output: 12   (2 + 9 + 1)

Each house has one decision: skip it and continue at i + 1, or rob it, gain nums[i] and continue at i + 2. So best(i) = max(best(i + 1), nums[i] + best(i + 2)).

Brute force: try both choices at every house

Java

class Solution {
    private int best(int[] nums, int i) {
        if (i >= nums.length) {
            return 0;
        }
        return Math.max(best(nums, i + 1), nums[i] + best(nums, i + 2));
    }

    public int rob(int[] nums) {
        return best(nums, 0);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.rob(new int[]{1, 2, 3, 1}));
        System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
        System.out.println(solution.rob(new int[]{}));
    }
}

Output

4
12
0

Time: O(2^n) (about φ^n), because the two recursive calls overlap. Space: O(n) stack.

Better: memoization

There are only n distinct values of i, so best(i) can be cached in an Integer[], where null marks an empty slot.

Java

class Solution {
    private int best(int[] nums, int i, Integer[] memo) {
        if (i >= nums.length) {
            return 0;
        }
        if (memo[i] != null) {
            return memo[i];
        }
        int v = Math.max(best(nums, i + 1, memo), nums[i] + best(nums, i + 2, memo));
        memo[i] = v;
        return v;
    }

    public int rob(int[] nums) {
        Integer[] memo = new Integer[nums.length]; // null means "not computed yet"
        return best(nums, 0, memo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.rob(new int[]{1, 2, 3, 1}));
        System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
        System.out.println(solution.rob(new int[]{}));
    }
}

Output

4
12
0

Time: O(n). Space: O(n).

Optimal: bottom-up with two variables

Go left to right. Let dp[i] be the best loot using the first i houses. Either skip house i - 1 (dp[i - 1]) or rob it (dp[i - 2] + nums[i - 1]). Only the two previous values matter, so keep them in variables.

house	money	skip = prev	rob = prev2 + money	best
2	2	0	0 + 2	2
7	7	2	0 + 7	7
9	9	7	2 + 9	11
3	3	11	7 + 3	11
1	1	11	11 + 1	12

Java

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0; // best up to i-2
        int prev1 = 0; // best up to i-1
        for (int money : nums) {
            int cur = Math.max(prev1, prev2 + money);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.rob(new int[]{1, 2, 3, 1}));
        System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
        System.out.println(solution.rob(new int[]{}));
        System.out.println(solution.rob(new int[]{5}));
    }
}

Output

Time: O(n). Space: O(1).