题解 | 跳跃游戏(二)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n <= 0) {
        cout << -1;
        return 0;
    }
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];

    const int INF = -1e9;
    vector<long long> dp(n, INF);
    dp[0] = nums[0]; // 起点分数

    for (int i = 0; i < n; ++i) {
        if (dp[i] == INF) continue; // 到不了
        for (int j = 1; j <= nums[i] && i + j < n; ++j) {
            dp[i + j] = max(dp[i + j], dp[i] + nums[i + j]);
        }
    }
    cout << (dp[n - 1] == INF ? -1 : dp[n - 1]);
    return 0;
}