跳躍游戲 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
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/394084.html
標籤：其他
上一篇：猜單詞游戲