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;}
};
