45.跳跃游戏 ii

题目链接：

https://leetcode.cn/problems/jump-game-ii/description/

题面：

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处：

0 <= j <= nums[i] 
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

 

示例 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
题目保证可以到达 nums[n-1]

``

## 解析：
用贪心去思考没有意义，得用动态规划;

dp 表示能跳到该位置的最小步数; 

```go
dp[0]=0
for i:=0;i<n;i++{
    for j:=0;j<i;j++{
        // 暴力扫一遍，如果有满足条件的 j，那么更新;
        if j+nums[j] >= i{ // j 一步能跳到 i
            dp[i] = min(dp[i], dp[j]+1)
        }
    }
}
return dp[n-1]

优化: 根据已经计算的状态来推断后续状态

dp[0]=0
for i:=0;i<n;i++{
    for j:=1 ; j<nums[i] && i+j<n ; j++ {
        dp[i+j] = min(dp[i+j],dp[i]+1) // 用 dp[i]+1 更新所有从 i 出发能到达的点
    }
}
return dp[n-1]

以下的优化稍微复杂, 看哔哩哔哩教程: https://www.bilibili.com/video/BV19HW6eWEoD/?spm_id_from=333.788&vd_source=9529002c63d8eefaf57e87e2c8193594

实际通过的代码:

func jump(nums []int) int {
	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	n := len(nums)
	dp := make([]int, n)

	for i := 1; i < n; i++ {
		dp[i] = n // 初始化为一个较大的值, 否则无法正确更新
	}

	dp[0] = 0
	for i := 0; i < n-1; i++ { // 扫到n-2即可, 因为最后一个不用再跳
		for j := 1; j <= nums[i] && i+j < n; j++ { //可以等于nums[i]
			dp[i+j] = min(dp[i+j], dp[i]+1) // 用dp[i]+1更新所有从i出发能到达的点
		}
	}
	return dp[n-1]
}