跳跃游戏Ⅱ————最少跳跃数 https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked
给定一个长度为 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]。

/* 判断【起点】到达【终点】的最小跳跃次数
        dp[0]       dp[n-1]
总长度n  非负整数数组num[3]————>最多可往后跳0/1/2/3步
(法一) 【动态规划】
        i从起点右侧（dp[1]）遍历至终点（dp[n-1]）
            对于i左侧所有的j，满足——  j可达    &&   j往后能到达i   
                                    dp[j]=true       num[j]+j>=i
                ==> 满足 【最小】 && 【要不要更新】(更新就左侧dp+1)
                dp[i]=min(dp[i], dp[j]+1)

(法二) 【背包】step
        i从起点（dp[0]）遍历至终点（dp[n-1]）
            step从1累加至num[i]————> 
                ==> 满足 【最小】 && 【要不要更新】(更新就左侧dp+1)
                dp[i+step]=min(dp[i+step], dp[i]+1)
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n; // 数组长度
    cin>>n;
    vector<int> nums(n), dp(n, INT_MAX); // dp应初始化全为 INT_MAX（跳跃数无穷大————>不可达）

    for(int i=0;i<n;i++){
        cin>>nums[i];
    }

    dp[0]=0;

    // 法一【j ——> i】
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(dp[j]!=INT_MAX && j+nums[j]>=i){
                dp[i]=min(dp[i], dp[j]+1);
            }
        }
    }
    cout<<dp[n-1]<<endl;

    // 法二 【i———每一个step————>】
    for(int i=0;i<n;i++){
        for(int step=1;step<=nums[i];step++){
            if (i + step < n) { // 防止数组越界
                dp[i+step]=min(dp[i+step], dp[i]+1);
            }
        }
    }
    cout<<dp[n-1]<<endl;

    return 0;
}
/* 输入
5
2 3 1 1 4
【ERROR】
（一）由于dp[i]是从起点到i的最小跳跃数
所以在初始化时————> dp应初始化全为 INT_MAX（跳跃数无穷大————>不可达）
===> 相应的法一中j可达： dp[j] != INT_MAX
（二）if (i + step < n) { // 防止数组越界
*/