Posted on | Edited on

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

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int[] memo;
    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return rob(nums, nums.length - 1);
    }

    private int rob(int[] nums, int i) {
        if (i < 0) return 0;
        if(memo[i]<0) memo[i]= Math.max(rob(nums, i - 2) + nums[i], rob(nums, i - 1));
        return memo[i];  
    }
}

DP without array link
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int rob(int[] nums) {
        int prevMax=0,currMax=0;
        for(int x:nums){
            int tmp=currMax;
            currMax=Math.max(prevMax+x,currMax);
            prevMax=tmp;
        }
        return currMax;
    }
}

0%