# 一道算法题-跳跃游戏 II

## 跳跃游戏 II

1 <= nums.length <= 104 0 <= nums[i] <= 1000

## 思路

### 方案一：动态规划

#### 代码

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
}

### 方案二：动态规划

#### 代码

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

### 方案三：贪心

#### 代码

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
}

THE END