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

解题思路：

• 超时坑点，从前往后推，简单明了的思路，dp[i]表示走到i点的最小步数，那么dp[0] = 1;对于i>0的点，有$j_{0:i-1},j+v[j]>=i,dp[i]=min(dp[j_0]:dp[j_{i-1}]+1)j\_\{0:i-1\},j+v[j]>=i,dp[i]\; =\; min(dp[j\_0]:dp[j\_\{i-1\}]+1)$,时间复杂度$O(n^2)O(n^2)$.
• 为解决超时问题，在dp过程中使用贪心策略。记录走过点中可以到达最远距离的点idx和其值v[idx]，当i走出这个点的时候，应该搜索前一次记录点到当前i位置之间可以到达距离最远的点（这就是贪心的策略），即在走的过程中总是往最远点跳，如果最远点不能到达终点，则应该从刚才最远点所能到达的距离内选择一个可以跳到最远的点，继续跳，得到的结果既是最小步数。

#include<bits/stdc++.h>
using namespace std;
int solve(vector<int> &v, vector<int> &dp, int n){
    if(n==0) return -1;
    dp[0] = 1;
    int idx = 0, mx = v[0];//第一个最远点
    for(int i = 1; i < n; ++i){
        if (i <= idx+mx) dp[i] = dp[idx]+1;//在最远点的范围内只要从记录的点跳一步到达
        else{//如果超出范围，则应该再次选择前区域中所能到达的最远点。
            int tmp_idx = idx, tmp_mx = mx;
            for(int j = idx; j <= idx+mx; ++j){
                if(j+v[j] > tmp_idx + tmp_mx){
                    tmp_idx = j;
                    tmp_mx = v[j];
                } 
            }
            mx = tmp_mx;
            idx = tmp_idx;
            if(i <= mx+idx) dp[i] = dp[idx] +1;
            else dp[i] = 0;//如果最远点都到达不了，则一定不能到达终点
        }
    }    
    return dp[n-1] == 0? -1: dp[n-1]-1;//判断是否可以到达终点，若可达则应该dp[n-1]-1，因为最后一个点不计次。
}
int main(){
    int n;
    cin >>n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        scanf("%d",&v[i]);//最大有10万个数据，可使用scanf加速
    vector<int> dp(n);
    cout<<solve(v, dp, n)<<endl;
    return 0;
}