#P4084. 跳跃游戏Ⅱ

跳跃游戏Ⅱ

题目内容

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

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

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

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

输入描述

输入一个数组

输出描述

输出一个整数表示最小跳跃次数

样例1

输入

2 3 1 1 4

输出

说明

跳到最后一个位置的最小跳跃数是 22

从下标为 00 跳到下标为 11 的位置,跳 11 步,然后跳3 3 步到达数组的最后一个位置。

样例2

输入

2 3 0 1 4

输出

提示:

  • 1<=nums.length<=1041 <= nums.length <= 10^4
  • 0<=nums[i]<=10000 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n1]nums[n-1]