刷题使我快乐，满脸开心.jpg
- 来源：力扣（LeetCode）
- 链接：https://leetcode.cn/problems/jump-game-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]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 题目保证可以到达
nums[n-1]
思路
有多种思路，最容易想到的应该就是贪心和动态规划了
-
贪心
每个都找能够跳到最远的地方，直到能到达的距离大于等于len(nums)，期间统计步数即可 -
动规
一维数组统计动规结果，dp数组下标为nums数组下标，值为到达当前位置所需的步数，所以就会有一个等式
dp(i+j) = dp(i)+1，j <=nums[i]
如此，当i从0到len(nums)遍历过去的时候，dp数组中存储的就是每个位置最小可到达的步数，直接返回dp[len(nums)-1]即可
代码
贪心
func jump(nums []int) int {
nextPosition := 0
maxPosition := 0
steps := 0
for i := 0; i < len(nums) - 1; i++ {
maxPosition = max(maxPosition, i + nums[i])
// 寻找完当前位置能到达最远位置之后，更换一个新的目标位置，继续在下一个目标位置之前能够到达的最远位置，最后一次更新的最远位置一定是等于或远于len(nums) - 1的，如果恰好等于，那还需要再走一步到终点， 如果大于，那就无需再走一步，直接返回
if i == nextPosition {
nextPosition = maxPosition
steps++
}
}
return steps
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
动态规划
func jump(nums []int) int {
dp := make([]int, len(nums))
for i = 0; i < len(dp); i++ {
// 最大不会超过n
dp[i] = len(nums)
}
// 初始位置无需移动，是0步
dp[0] = 0
for i = 0; i <= len(dp)-1; i++ {
for j := 1; j <= nums[i]; j++ {
// 可以走到的范围内，均把从上一个位置跳过来+1步的结果和原有结果作比较，
// 更小则更新，这样可以得到一个到达每一个位置的最小步数
if i+j < len(nums) && dp[i+j] > dp[i]+1 {
dp[i+j] = dp[i] + 1
}
}
}
return dp[len(dp)-1]
}