House Robber II solution base on House Robber I


  • 0
    Q
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        if(len == 1) return nums[0];
        int[] dp = new int[len];
        int use, inuse;
        //the first element used, so the last element can not be used
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        use = dp[len-2];
        //the first element is not used, so the last element can be used
        dp[0] = 0;
        dp[1] = nums[1];
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        inuse = dp[len-1];
        return Math.max(use, inuse);
    }

  • 0
    L

    Can you guarantee that nums[0] is used in the first loop?


Log in to reply
 

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