198. House Robber

1.递归, 见递归树，黄色为重叠部分结果

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

public int tryRob(int[] nums, int index) {
    if (index >= nums.length) return 0;
    int res = 0;
    for (int i = index; i < nums.length; i++) {
        res = Math.max(res, nums[i] + tryRob(nums, i + 2));
    }
    return res;
}

2.memo, 为index添加缓存

public int rob(int[] nums) {
    int[] memo = new int[nums.length];
    Arrays.fill(memo, -1);
    return tryRob(nums, 0, memo);
}

public int tryRob(int[] nums, int index, int[] memo) {
    if (index >= nums.length) return 0;
    if (memo[index] != -1) return memo[index];
    int res = 0;
    for (int i = index; i < nums.length; i++) {
        res = Math.max(res, nums[i] + tryRob(nums, i + 2, memo));
    }
    memo[index] = res;
    return res;
}

3.dp

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