1.动态规划（很不幸，超时了）

思路

设dp[i]为跳到第i个位置需要的最少步数。

初始条件，设跳到每个位置的步数都是无穷大。

        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

要知道dp[i]的最少步数，就要知道从哪个位置起跳能到i，遍历数组元素，如果从当前位置j起跳，跳nums[j]步，能跳到i位置，那么dp[j]+1和当前dp[i]比，小的那个就是最少步数。

                if(nums[j] + j >=i)
                    //从j位置能跳到i位置
                    dp[i] = Math.min(dp[i],dp[j]+1);
            }

代码

 1     public int jump(int[] nums) {
 2         int[] dp = new int[nums.length];
 3         for (int i = 1; i < dp.length; i++) {
 4             dp[i] = Integer.MAX_VALUE;
 5         }
 6 
 7         for (int i = 1; i < dp.length; i++) {
 8             for (int j = 0; j < i; j++) {
 9                 if(nums[j] + j >=i)
10                     //从j位置能跳到i位置
11                     dp[i] = Math.min(dp[i],dp[j]+1);
12             }
13         }
14         return dp[nums.length-1];
15     }

2.贪心

思路

从当前位置i起跳，可以跳到[i+1,nums[i]+i]个候选位置，从i位置起跳后的位置应该是候选位置中能跳的最远的位置。

根据这个思路，设定point指针指向当前位置，maxIndex表示当前位置能起跳到的最远位置。

 1         while(point < nums.length){
 2             int maxIndex = nums[point] + point;
 3             //如果最远位置能到终点，直接跳到终点
 4             if(maxIndex >= nums.length -1){
 5                 step++;
 6                 break;
 7             }
 8             //max保存候选位置能到的最远位置
 9             int max = 0;
10             for (int i = point; i <= maxIndex; i++) {
11                 if(i+nums[i] >= max){
12                     point = i;
13                     max = i+nums[i];
14 
15                 }
16             }
17             step++;
18         }

边界条件

注意这块的等号，多个候选位置能到同一个最远距离的时候，point指向后边的候选位置。

if(i+nums[i] >= max)

代码

 1     public int jump(int[] nums) {
 2         if(nums.length == 1)
 3             return 0;
 4         int point = 0;
 5         int step = 0;
 6         while(point < nums.length){
 7             int maxIndex = nums[point] + point;
 8             if(maxIndex >= nums.length -1){
 9                 step++;
10                 break;
11             }
12             int max = 0;
13             for (int i = point; i <= maxIndex; i++) {
14                 if(i+nums[i] >= max){
15                     point = i;
16                     max = i+nums[i];
17 
18                 }
19             }
20             step++;
21         }
22         return step;
23     }

45. 跳跃游戏 II

1.动态规划（很不幸，超时了）

思路

代码

2.贪心

思路

边界条件

代码