力扣题解（跳跃游戏II）

本文主要是介绍力扣题解（跳跃游戏II），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

思路：

解法一是利用递归的思想，从后往前，dp[i]表示从i位置到n-1的最小跳跃次数，最后dp[0]就是从0跳到n-1位置的最小次数。

解法二是层序遍历的思想，l和r表示当前跳跃次数所能到达的范围（此处的范围是被上一次跳跃范围不共同包含的那一部分），最后看哪一次跳跃后范围包括n-1，则跳跃次数就是那一次。

class Solution {
public:int jump(vector<int>& nums) {// int n=nums.size();// if(n==1)// return 0;// vector<int>dp(n,INT_MAX-1000);// dp[n-1]=1;// for(int i=n-2;i>=0;i--)// {//    for(int j=0;j<=nums[i];j++)//    {//      if(i+j>=n-1)//      {//         dp[i]=1;//         break;//      }//      else//      {//         dp[i]=min(dp[i],dp[i+j]+1);//      }//    }// }// return dp[0];int n=nums.size();int l=0,r=0;int ret=0;while(r<n-1){   // cout<<l<<r;ret++;int l1=r+1;int r1=r;for(int i=l;i<n&&i<=r;i++){r1=max(r1,i+nums[i]);}l=l1;r=r1;}return ret;}
};

这篇关于力扣题解（跳跃游戏II）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---