Only need to change a little on House Robber I.


  • 0
    L

    Basic concept: We must give up either nums[0] or nums [1].

    And after giving up one of them, it is House Robber I again.

    public class Solution {
        public int rob(int[] nums) {
            if (nums.length == 0) return 0;
            if (nums.length == 1) return nums[0];
            int[] tmp1 = new int[nums.length-1];
            int[] tmp2 = new int[nums.length-1];
            for (int i = 0; i < nums.length-1; i ++){
                tmp1[i] = nums[i];
                tmp2[i] = nums[i+1];
            }
            return Math.max(subRob(tmp1),subRob(tmp2));
        }
        
        
        public int subRob(int[] nums) {
            int max = 0;
            if (nums.length == 0) return 0;
            if (nums.length == 1) return nums[0];
            if (nums.length == 2) return Math.max(nums[0],nums[1]);
            int first = nums[0];
            int second =  Math.max(nums[0],nums[1]);
            for (int i = 2; i < nums.length; i ++){
                max = Math.max(first + nums[i], second);
                first = second;
                second = max;
            }
            return max;
        }
    }
    111

Log in to reply
 

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