跳跃游戏 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),不是特别高效,不过好歹能过。
代码
1 | var recordJump map[int]int |
方案二:动态规划
分析
方案一是从头到尾计算,我们完全可以改为从尾到头计算,因为后面计算出的每一个f(n)都是准确的,这样也无需递归计算。
代码
1 | var recordJump map[int]int |
方案三:贪心
分析
贪心思路和方案一有点类似。其核心思路是,如果从0开始跳,最远能跳到7;下一跳的最远位置,必然是1~7上能跳到的最远位置;每次到达最远位置,意味多跳了一次。
贪心的效率是最高的,但是,也是比较难想到的。
代码
1 | func jump3(nums []int) int { |