Leetcode 45 jumping game II

LeetCode45 Jumping game II

Title Description

Given an array of nonnegative integers , You are first in the array .

Each element in the array represents the maximum length you can jump at that location .

Your goal is to reach the last position of the array with the least number of jumps .

Examples

 Input : [2,3,1,1,4]
 Output : 2
 explain :  The minimum number of jumps to the last position is  2.
      From the subscript for  0  Jump to subscript  1  The location of , jump  1  Step , Then jump  3  Step to the last position of the array .

Algorithm analysis

• f[i] All from 0 Position reached i The minimum number of steps in the position
• j Is to find from j Jump to the i, Jump to the i There are many ways , And from j To i It's the first road ,f[i] = f[j]+1

Time complexity

\(O(n)\)

Java Code

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+10];
        for(int i = 1, j = 0; i<n; i++){
            while(j + nums[j] < i) j++;
            f[i] = f[j] + 1;
        }
        return f[n-1];
    }
}