Leetcode 45) Jump Game II

20 Aug 2021 in Algorithms

내 답안

class Solution {
    int[] dp ;
    public int jump(int[] nums) {
        dp = new int[nums.length+1];
        Arrays.fill(dp,-1);
        return jg(nums,0);
    }
    
    public int jg(int nums[],int start){
        if(start==nums.length-1){
            dp[start]=0;
            return 0;
        }
        if(dp[start]!=-1){
            return dp[start];
        }
        int end = nums[start];
        if(end ==0){
            //return maxvalue위험. +1 더해지면 음수로 되고, min 함수 쓸때 위험하다.
            return 1001;
        }
        
        int min = Integer.MAX_VALUE;
        for(int i=start+1; i<=start+end;i++){
            if(i>=nums.length){
                dp[i]=1;
                return 1;
            }
            int tmp=jg(nums,i);
            dp[i]=tmp;
            if(min>tmp){
                min=tmp;
            }
        }
        
        return 1+min;        
    }
    
}

다른 답안

class Solution {
    public int jump(int[] nums) {
        int res = 0;
        if (nums != null && nums.length > 1) {
            res++;
            int startIndex = 0;
            int endIndex = nums[0];
            while (endIndex < nums.length - 1) {
                res++;
                startIndex = Math.min(nums.length - 1, findIndexOfMax(nums, startIndex + 1, endIndex));
                endIndex = startIndex + nums[startIndex];
            }
        }
        return res;
    }
    
    private int findIndexOfMax(int[] nums, int startIndex, int endIndex) {
        int max = 0;
        int res = 0;
        for (int i = startIndex; i <= endIndex; i++) {
            if (i >= nums.length) {
                break;
            }
            int current = i + nums[i];
            if (current >= max) {
                max = current;
                res = i;
            }
        }
        return res;
    }
}