leetcode面试经典150题- 45. 跳跃游戏 II

https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

go

package leetcode150

import "testing"

func TestJump2(t *testing.T) {
    nums := []int{5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0}
    res := jump3(nums)
    println(res)
}

func jump3(nums []int) int {
    ff := make([]int, len(nums))
    for i := len(nums) - 2; i >= 0; i-- {
        if i+nums[i] >= len(nums)-1 {
            ff[i] = 1
        } else {
            for j := i + 1; j <= i+nums[i]; j++ {
                if ff[j] != 0 && (ff[i] == 0 || ff[i] > 1+ff[j]) {
                    ff[i] = 1 + ff[j]
                }
            }
        }
    }
    return ff[0]
}

func jump2(nums []int) int {
    if len(nums) <= 1 {
        return 0
    }
    ff := make([]int, len(nums))
    return jumpHandler(nums, ff, 0)
}

func jumpHandler(nums []int, ff []int, pos int) int {
    if nums[pos] == 0 {
        return 0
    }

    if ff[pos] > 0 {
        return ff[pos]
    }

    if pos+nums[pos] >= len(nums)-1 {
        ff[pos] = 1
        return ff[pos]
    }

    minStep := 0
    for i := nums[pos]; i > 0; i-- {
        s := jumpHandler(nums, ff, pos+i)
        if minStep == 0 || (minStep > s && s != 0) {
            minStep = s
        }
    }
    ff[pos] += minStep + 1

    return ff[pos]
}