给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
提示:
1 <= nums.length <= 104 0 <= nums[i] <= 1000
思路代码位置为：https://github.com/shidawuhen/asap/blob/master/controller/algorithm/45-jump-game-ii.go
方案一：动态规划分析动态规划公式如下图所示：
举个例子，如果从位置0开始跳，因为值为7，所以可以选择跳到17的位置上，而且必然需要跳一次，那么只要选择17上，谁跳到最后一个位置用的跳跃次数最少即可。
按这个思路，使用递归，同时使用数组记录每个位置跳到最后位置最少跳跃次数即可。
时间复杂度的话，O(n*m)，不是特别高效，不过好歹能过。
代码var recordJump map[int]int
func jump(nums []int) int {
if len(nums) == 1 {
return 0
}
recordJump = make(map[int]int, 0)
recordJump[len(nums)-1] = 0
return countJump(0, nums)
}
func countJump(index int, nums []int) int { //从index到末尾最短路径
if index >= len(nums)-1 {
return 0
}
minJump := 100000
for i := 0; i < nums[index] && i 1 index < len(nums); i {
j := 0
if _, ok := recordJump[i 1 index]; ok {
j = recordJump[i 1 index]
} else {
j = countJump(i 1 index, nums)
}
j = 1 j
if j < minJump {
minJump = j
}
}
recordJump[index] = minJump
return minJump
}
方案二：动态规划分析
方案一是从头到尾计算，我们完全可以改为从尾到头计算，因为后面计算出的每一个f(n)都是准确的，这样也无需递归计算。
代码var recordJump map[int]int
func jump(nums []int) int {
if len(nums) == 1 {
return 0
}
recordJump = make(map[int]int, 0)
recordJump[len(nums)-1] = 0
for index := len(nums) - 2; index >= 0; index-- {
//根据自身能跳跃的长度，找到最小值
minJump := 1000000
for i := index 1; i < index 1 nums[index] && i < len(nums); i {
jump := 1 recordJump[i]
if jump < minJump {
minJump = jump
}
}
recordJump[index] = minJump
}
return recordJump[0]
}
方案三：贪心分析
贪心思路和方案一有点类似。其核心思路是，如果从0开始跳，最远能跳到7；下一跳的最远位置，必然是1~7上能跳到的最远位置；每次到达最远位置，意味多跳了一次。
贪心的效率是最高的，但是，也是比较难想到的。
代码func jump3(nums []int) int {
if len(nums) == 1 {
return 0
}
maxPoint := 0
targetPoint := nums[0]
jump := 0
for i := 0; i < len(nums); i {
if i nums[i] > maxPoint {
maxPoint = i nums[i]
}
if i == targetPoint || i == len(nums)-1 {
jump
targetPoint = maxPoint
}
}
return jump
}
