Leetcode 213) House Robber II

03 Jun 2021 in Algorithms

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int[]dp1 =new int[nums.length] ;
        int[]dp2 =new int[nums.length] ;

        dp1[0]=0;dp1[1]=nums[0]; dp2[0]=0;dp2[1]=nums[1];

        for(int i =1;i<nums.length-1;i++){
            dp1[i+1]= Math.max(dp1[i],dp1[i-1]+nums[i]);

        }
        for(int i =2;i<nums.length;i++){
            dp2[i]= Math.max(dp2[i-1],dp2[i-2]+nums[i]);   

        }

        int max= Math.max(dp1[nums.length-1],dp2[nums.length-1]);
        return max;
    }
}

• 어레이 그림 그려보기

다른 답안

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(helper(nums, 0, nums.length - 2), helper(nums, 1, nums.length - 1));     
    }

    public int helper(int[] nums, int start, int end) {
        int[] dp = new int[end - start + 2];
        dp[0] = 0;
        dp[1] = nums[start];
        for (int i = 1; i < dp.length - 1; i++) {
            int value = nums[start + i];
            dp[i + 1] = Math.max(dp[i], dp[i-1] + value);
        }
        return dp[dp.length - 1];
    }
}