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

解题思路：

• 不能递归了，递归栈真的会炸。
• 递推进行，不能常规地从左往右推，而应该从右往左推，即答案位于dp[0]。
• 先讨论一般情况，dp[i]表达的是此位置能到达n-1位置所能得到的最大分数。那么对于任一位置i有：$dp[i]=max(d{p}_{i+1:n-1}+v[i])dp[i]\; =\; max(dp\_\{i+1:n-1\}+v[i])$即i位置往后走的过程中所能选取可以到达n-1的最大分+当前位置的分数。
• 再讨论边界，当i = n-1时，分数即是v[n-1]，这里有个特例，当v[n-1] = 0时，应该特殊处理，因为在中间过程中如果走不下去dp值会变0，所以要加以区分。

#include<bits/stdc++.h>
using namespace std;
//一样的逻辑，这一版递归炸了
// int solve(vector<int> &v, int i,int n, vector<int> &dp){
//     if(dp[i] != -1) return dp[i];
//     if(i >= n-1) dp[i] = v[i];
//     else{
//         int tmp = -3;
//         if(v[i] > 0){
//             int flag = 0;
//             for(int j = 1; j <= v[i]; ++j){
//                 if (i+j == n-1){
//                     flag = 1;
//                 }
//                 tmp = max(tmp,solve(v, i+j, n, dp));
//             }
//             if (flag) dp[i] = v[i] + tmp;
//             else
//                 dp[i] = tmp == 0? 0: tmp+v[i];
//         }
//         else dp[i] = 0;  
//     }
//     return dp[i];
// }
int solve2(vector<int> &v, vector<int> &dp, int n){
    dp[n-1] = v[n-1];//当只有一个点时，cost=v[i]
    for(int i = n-2; i >= 0; --i){
        if(v[i] > 0){//当所进过的点的值>0时，应选取可以到达结果的最大分数作为结果。
            int flag = 0;
            int tmp = -3;
            for(int j = 1; j <= v[i]; ++j){
                if(i+j >= n-1){
                    flag = 1;//flag来标记最后一个值为0的情况。
                    tmp = max(tmp, dp[n-1]);
                    break;
                }
                tmp = max(tmp, dp[i+j]);//一般情况
            }
            if(flag) dp[i] = tmp + v[i];
            else dp[i] = tmp == 0? 0: tmp+v[i];
        }
        else dp[i] = 0;
    }
    return dp[0];
}
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        scanf("%d",&v[i]);
    }
    vector<int> dp(n, -1);
   int ans;
   ans = (n==0?0:solve2(v, dp, n));

    cout<<(ans == 0? -1: ans)<<endl;
    return 0;
}