45. 跳跃游戏 II

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

func jump(nums []int) int {
    // 动态规划四步走：
    // 1、状态：f[i] 表示从起点到当前位置跳的最小次数
    // 2、推导：f[i] = min(f[j]+1),a[j])  j >=i 表示从j位置用一步跳到当前位置，这个j位置可能有多个，取最小的一个就行
    // 3、初始化：f[0] = 0
    // 4、结果：f[n-1]
    f := make([]int, len(nums))
    f[0] = 0
    for i := 1; i < len(nums); i++ {
        // f[i] 先取一个默认最大值i
        f[i] = i
        // 遍历之前结果取一个最小值+1
        for j := 0; j < i; j++ {
            if nums[j]+j >= i {
                f[i] = min(f[j]+1,f[i])
            }
        }
    }
    return f[len(nums)-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func jump(nums []int) int {
    if nums == nil || len(nums) == 0{
        return -1
    }
    
    n := len(nums)
    count,max,end := 0,0,0
    for i:=0;i<n-1;i++{
        
        // 记录每一个位置i所能跳到的最大位置max
        if i+nums[i]>max{
            max = i+nums[i]
        }
        // end是上一个所选的起跳位置能跳的最远处，当到达end时，更新下一跳的最大位置
        if i == end{
            end = max
            count++
        }
    }
    return count
}