一道算法题-跳跃游戏 II

跳跃游戏 II

给你一个非负整数数组 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
}