0ms java solution using dp,O(n) time, with explanation


  • 8
    L

    let sum[i] be the maximum amount of money when robber comes at i, he can either rob it or not depending on the money robbed at i-1 and i-2.

    corner case: sum[0] = num[0], sum[1] = max(num[0],num[1])

    generally, at position i, sum[i] = max(sum[i-1], sum[i-2]+num[i])

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

    Another approach is to use two variables to store sum[i-1] and sum[i-2] iteratively in the previous program. This approach avoids building an array to store all of the sums, which only uses O(1) space.

    public int rob(int[] nums) {
        int size = nums.length;
        if(size == 0) return 0;
        if(size == 1) return nums[0];
        if(size == 2) return Math.max(nums[0],nums[1]);
        int minusOne = Math.max(nums[0],nums[1]), minusTwo = nums[0], sum = minusOne;
        for(int i = 2;i<size;i++){
            sum = Math.max(minusOne, minusTwo+nums[i]);
            minusTwo = minusOne;
            minusOne = sum;
        }
        return sum;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.