题解 | #跳跃游戏(三)#

#include <iostream>
#include<cstring>
using namespace std;

const int N = 100010;
int a[N], f[N];

int minJump(int n){
    if(n == 0) return -1;
    f[0] = 0;
    for(int i = 0; i < n; i ++){
        if(f[i] != -1){
            int maxReach = min(i + a[i], n - 1);
            for(int j = i + 1; j <= maxReach; j ++){
                f[j] = min(f[j], f[i] + 1);
            }
        }
    }
    return f[n - 1];
}

int main() {
    int n;
    cin >> n;
    memset(f, 0x3f, sizeof f);
    for(int i = 0; i < n; i ++) cin >> a[i];
    if(minJump(n) == 0x3f3f3f3f) cout << "-1" << endl;
    else cout << minJump(n) << endl;
    return 0;
}