1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

    private int dp(int[] nums,int start,int[] memo){
        if(start>=nums.length){
            return 0;
        }

        if(memo[start]!=-1){
            return memo[start];
        }
        int ans = Math.max(dp(nums, start+1,memo),nums[start]+dp(nums, start+2,memo));
        memo[start]= ans;
        return ans;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int rob(int[] nums) {
        int n = nums.length;
        int[] memo1 = new int[n + 1];
        int[] memo2 = new int[n + 1];
        Arrays.fill(memo1, -1);
        Arrays.fill(memo2, -1);
        int case1 = dp(nums, 0, n - 2, memo1);
        int case2 = dp(nums, 1, n - 1, memo2);
        return Math.max(case1, case2);
    }

    private int dp(int[] nums, int start, int end, int[] memo) {
        if (start > end) {
            return 0;
        }

        if (memo[start] != -1) {
            return memo[start];
        }
        int ans = Math.max(dp(nums, start + 1, end, memo), nums[start] + dp(nums,
                start + 2, end, memo));
        memo[start] = ans;
        return ans;
    }