https://leetcode.com/problems/house-robber/

recursive function

Define rob(i, 1) as the max money we can get if we rob the ith house, rob(i, 0) as max money we can get if we don’t rob ith house. Then:

1
2
rob(i, 1) = rob(i - 1, 0) + nums[i] // i-1 th house can't be robbed
rob(i, 0) = max(rob(i - 1, 1), rob(i - 1, 0)) // doesn't matter if i-1 th hosue is robbed

Then, based on the idea above:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int rob(int[] nums) {
    if (nums == null || nums.length < 1) {
         reurn 0;
    }
    return Math.max(rob(nums, nums.length - 1, 1), rob(nums, nums.length - 1, 0));
}
private int rob(int[] nums, int num, int rob) {
    if (num == 0) {
        if (rob == 1) {
           reuturn nums[0];
        } else {
            return 0;
        }
    }
    if (rob == 0) {
        return Math.max(rob(nums, num - 1, 0), rob(nums, num - 1, 1));
    } else {
        return rob(nums, num - 1, 0) + nums[num];
    }
}

The complexity of this is O(2^n), which need be to optimized.
We can use dynamic programming to store the intermedia result by use a 2-D array:

int[][] dp = new int[nums.length][2]

dp[i][0] is for ith house, the max money we get if we don’t rob, dp[i][i] as the max money we can get if we rob the house i;

dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0]);
dp[i][1] = dp[i - 1][0] + nums[i];

further optimize

We don’t need a 2-D array to keep all the intermedia result for us, only the prevRob and preNotRob is needed.