O(n) and only one dimensional dp


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

Log in to reply
 

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