Easy java solution using DP


  • 11
    D

    public class Solution {
    public int rob(int[] nums) {

        //if nums is null or length 0, return 0
        if(nums==null || nums.length==0)
            return 0;
            
        //if only 1 element is present,return it as the answer
        if(nums.length==1)
            return nums[0];
            
        //array to store the maxProfit attained
        int[] maxProfit=new int[nums.length];
        
        //assign fisrt value
        maxProfit[0]=nums[0];
        
        //second value is higher of first and second
        maxProfit[1]=Math.max(nums[0],nums[1]);
        
        //do dynamic programming for subsequent values
        for(int i=2;i<nums.length;i++)
        {
            maxProfit[i]=Math.max(maxProfit[i-2]+nums[i],maxProfit[i-1]);
        }
        
        //return the last value as answer
        return maxProfit[nums.length-1];
    }
    

    }


  • 4
    Y
    public class Solution {
    public int rob(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        
        int n0 = 0;  // 记录没有选择当前houses时的获取的最大金额
        int n1 = 0;  // 记录选择当前houses时的获取的最大金额
        for(int i=0; i<nums.length; i++){
            int tmp = n0;
            n0 = Math.max(n0,n1);  //没有选择当前houses,那么它等于上次选择了或没选择的最大值  
            n1 = tmp+nums[i];  //选择了当前houses,值只能等于上次没选择的+当前houses的money
        }
        
        return Math.max(n0, n1);
    }
    

    }


  • 0
    A

    @yinshuisiyuan - can you please explain your solution?


  • 0
    Y

    n0 is the max money he can get if he do not select the current house. n1 is the max money he can get if he select the current house. And we scan nums. If he does not select the current house, n0 would be the bigger number in the n0 and n1 of the last time. If he select the current house, he certainly not select the last house. So if he want to get the max money, he should select the current house, and the n1 at this time is the n0 of last time(tmp in the program) plus the money in the current house. The result is the bigger number in n0 and n1.


  • 0
    R

    Thanks for sharing, and here is the code without extra space:

    public int Rob(int[] nums) {
        if (nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];
    
        nums[1] = Math.Max(nums[0], nums[1]);
        
        for(int i =2; i < nums.Length ; i++)
        {
            nums[i] = Math.Max(nums[i-1], nums[i] + nums[i-2]);
        }
        return Math.Max(nums[nums.Length -1], nums[nums.Length -2]);    
    }

Log in to reply
 

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