O(n), DP


  • 0
    Z
    public int jump(int[] nums) {
            int[] dp = new int[nums.length];
            
            // dp pointer
            int j=1;
            for (int i=0; i<nums.length; i++) {
                int loc= nums[i] + i;
                while (j<=loc && j<nums.length) {
                    dp[j] = dp[i] + 1;
                    j++;
                }
            }
            
            return dp[dp.length-1];
        }
    

Log in to reply
 

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