LeetCode 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

如果从后往前想，即用递归的思想来思考，会得到比较差的算法，时间复杂度会达到O(n^2)

如果从前往后想，就会想到时间复杂度为O(n)的算法，设置d[i]代表到达i位置需要的跳数，每个d[i]只修改一次，所以是O(n)的时间复杂度。该思想有点类似于BFS

这里采用的是O(n)的空间复杂度，还可以继续优化到O(1)的空间复杂度

 1 int d[1000000]={0};
 2 int jump(int* nums, int numsSize) {
 3     if(numsSize==1)return 0;
 4     int hasNumPlace=0;
 5     int endPlace=0;
 6     for(int i=0;i<numsSize-1;i++){
 7         if(i+nums[i]>numsSize-1) //out of nums range
 8             endPlace=numsSize-1;
 9         else 
10             endPlace=i+nums[i];
11         
12         for(int j=hasNumPlace+1;j<=endPlace;j++){
13             d[j]=d[i]+1;
14         }
15        
16         if(hasNumPlace<i+nums[i])
17             hasNumPlace=i+nums[i];
18         if(hasNumPlace==numsSize-1)
19             break;
20     }
21     return d[numsSize-1];
22 }