Leetcode 198) House Robber

02 Jun 2021 in Algorithms

• Dynamic programming 에 속한다는데. 왜 array에 있는가? 흠..
• https://www.youtube.com/watch?v=ZwDDLAeeBM0 이 영상보고 공부함.

class Solution {
    public int rob(int[] nums) {
        int[] max=new int[nums.length+1];
        max[0]=0;
        max[1]=nums[0];
        for(int i=1;i<nums.length;i++){
            max[i+1]= Math.max(max[i],max[i-1]+nums[i]);
        }
        return max[nums.length];
    }
}

다른 답안

class Solution {
    int solve(int[] nums, int i,int[] dp){
        if(i>=nums.length) return(0);
        if(dp[i]!=-1) return(dp[i]);
        return(dp[i]=Math.max(solve(nums,i+1,dp),nums[i]+solve(nums,i+2,dp)));
    }
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,-1);
        return(solve(nums,0,dp));
    }
}