DP Java O(n) solution with no extra space


  • 0
    T

    The first 3 houses should be self-explained. Starting from the 4th house, we need to consider the n-2 and n-3 since we know n-1 is not possible.

    public class Solution {
        public int rob(int[] num) {
            if(num.length == 0)
                return 0;
            if(num.length == 1)
                return num[0];
            if(num.length == 2)
                return Math.max(num[0], num[1]);
            if(num.length == 3)
                return Math.max(num[0]+num[2], num[1]);
                
            num[2] += num[0];
            for(int i=3; i<num.length; i++)
                num[i] += Math.max(num[i-2], num[i-3]);
                
            return Math.max(num[num.length-2], num[num.length-1]);
        }
    }

Log in to reply
 

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