DP solution in java with explaination, easily understand, 0ms


  • 1
    H

    define rob[i] as the maximum amount of money can rob from the first i houses.

    rob[0] = nums[0];
    rob[1] = max(nums[0],nums[1]);
    rob[i] = max(nums[i]+rob[i-2], rob[i-1]);
    

    so,the code:

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

  • 1
    B

    just a quick correction, In the explanation, nums array is also referred as "m"


  • 0
    H

    sorry, it‘s a clerical error in the explanation, you understand right, thank you for pointing out the problem


Log in to reply
 

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