45. 跳跃游戏 II(Hard)

题目描述

给定一个非负的数组代表在该位置可以跳的最大长度，目前你处于数组的开头，问最少需要几跳可以跳到数组的末尾

样例

Input: nums = [2,3,1,1,4]
Output: 2
# 索引0 跳1步到 索引1，索引1跳3步到末尾

题解

本题是跳跃游戏的进阶版，只是跳跃游戏求可达性，本题求最小步数。

首先，可以用动态规划，很容易建立转移方程

• dp[i] = min(dp[i], dp[j] + 1) j <= i 且 j 可以在 nums[j] 步调到 i

只是这样的代码 Python 等语言容易超时

代码示例

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

func jump(nums []int) int {
    n := len(nums)
    if n < 2 {
        return 0
    }

    dp := make([]int, n)
    for i := 0; i < n; i ++ {
        dp[i] = math.MaxInt64 // 求最小，默认是放最大
      // 也可以是 dp[i] = i // 其实本题从题意分析，前 i 个元素，最大的跳跃步数就是i，也就是一格格跳(非负)
    }

    dp[0] = 0

    for i := 1; i < n; i ++ {
        for j := 0; j < i; j ++ {
            if i - j <= nums[j] { // 可以从 j 跳到 i
                dp[i] = min(dp[i], dp[j] + 1)
            }
        } 
    }
    return dp[n - 1]    
}

本题Go 可以跳到，但是 Python 等会超时，需要使用贪心法优化一下。

我们发现这里可以有优化的地方，当我们求访问 i 位置的最小值的时候，可以直接返回第一个从左向右找到的值。

比如样例中 [2, 3, 1, 1, 4]，对于索引 3 的 1来说，有 2 -> 1, 3 -> 1, 1 -> 1 三种跳法，但是细想我们只需要考虑第一个元素 2 的情况即可，因为从 2 跳 一定是最优的。因为 2 可以调到 3，1。所以对于 3， 1 来说，他们的最优跳数一定是小于等于 2 的。

从 dp 来看，其最终的值为 [0 1 1 2 2]，可以看出跳跃次数的结果集是单调递增的，所以贪心思路是正确的

动态规划 + 贪心策略

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

func jump(nums []int) int {
    n := len(nums)
    if n < 2 {
        return 0
    }

    dp := make([]int, n)
    for i := 0; i < n; i ++ {
        dp[i] = math.MaxInt64
    }

    dp[0] = 0

    for i := 1; i < n; i ++ {
        for j := 0; j < i; j ++ {
            if i - j <= nums[j] {
                dp[i] = min(dp[i], dp[j] + 1)
                break // 只增加了这一行，Go的耗时从 1000ms 降低到了 344ms
            }
        } 
    }
    return dp[n - 1]