本文共 1188 字，大约阅读时间需要 3 分钟。

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: [2,3,1,1,4]

输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 示例 2:

输入: [2,3,0,1,4]

输出: 2

提示:

1 <= nums.length <= 1000

0 <= nums[i] <= 105 通过次数124,113提交次数3

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/jump-game-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

C++

方法1：动态规划法

class Solution {
   public:    /*动态规划  时间复杂度：O(n^2)*/    int jump(vector
   
    & nums) {
           //dp[i]表示从起点跳到i处的最小step        vector
    
      dp(nums.size(),INT_MAX);        dp[0]=0;        for(int i=0;i
    
   

法二：

贪心

class Solution {
   public:    /*贪心算法：如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。    遍历到一个下标I，找到下一步可以跳跃的区间，求区间内第二次再跳可以达到的最大值    时间复杂度O(n)    */    int jump(vector
   
    & nums) {
                   int res=0; //返回的结果        int end=0;  //当前元素可以跳到的边界        int maxpos=0;  //当前可以走到的最远举例        for(int i=0;i
    
     =i){
                   maxpos=max(maxpos,i+nums[i]); //求可跳区间内下一次可达的最大值                if(i==end){
                       end=maxpos;                    res++;  //每次马上要越界了就需要跳一次                }            }        return res;    }};