C++ 解法, 执行用时: 12ms, 内存消耗: 1164KB, 提交时间: 2022-04-22

#include<iostream>
using namespace std;
const int MAXN = 1e5+5;
int n;
int arr[MAXN];
int step[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> arr[i];
    int curMax = arr[0];//记录最大可达
    step[0] = 0;//初始化
    for(int i = 0; i < n && i < arr[0]; ++i)
        step[1+i] = 1;
    for(int i = 1; curMax < n-1 && i <= curMax; ++i){//从后往前更新，保证步数最小
        for(int k = (i + arr[i]) >= n ? n-1 : i+arr[i]; !step[k]; --k)
            step[k] = step[i]+1;
        curMax = max(curMax, i+arr[i]);
    }
    if(curMax >= n-1)
        cout << step[n-1];
    else cout << -1;
    
    
    return 0;
}

C++ 解法, 执行用时: 13ms, 内存消耗: 804KB, 提交时间: 2022-02-17

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int,int> P;
const int MAXN = 2e5 + 10;
const int INF = 2e9;
int a[MAXN];
int dp[MAXN] = {0};
int main(){
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    rep(i,0,n) cin >> a[i];
    if(!n){
        cout << -1 << endl;
        return 0;
    }
    int ans = 0, maxpos = 0, end = 0;
    rep(i,0,n){
        if(i <= maxpos){
            maxpos = max(maxpos,i+a[i]);
            if(i == end){
                end = maxpos;
                if(i!=n-1)ans++;
            }
        }
        else {
            ans = -1;
            break;
        }
       
    }
    cout << ans << endl;
    return 0;
}

C++ 解法, 执行用时: 13ms, 内存消耗: 1180KB, 提交时间: 2022-05-07

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    if(n==0) printf("-1");
    else{
        int nums[100005];
        for(int i=0;i<n;++i){
            scanf("%d",&nums[i]);
        }
        int dp[100005];
        dp[0]=1;
        int start =0,len = nums[0];
        for(int i=1;i<n;++i){
            if(i<=start+len){
                dp[i] = dp[start]+1;
            }else{
                int start1=start,len1 = len;
                for(int j=start;j<=len+start;++j){
                    if(j+nums[j]>start1+len1){
                        start1 = j,len1 = nums[j];
                    }
                }
                start = start1,len = len1;
                if(i<=start +len) dp[i] = dp[start]+1;
                else dp[i]=0;
            }
        }
        printf("%d",(dp[n-1]==0?-1:dp[n-1]-1));
    }
}
    

C 解法, 执行用时: 14ms, 内存消耗: 680KB, 提交时间: 2022-02-17

#include <stdio.h>

int max(int a,int b)
{
    return a>b?a:b;
}
int min(int a,int b)
{
    return a<b?a:b;
}

int main() {
   
    long long n,i,j,maxnum=0;
    int sub=0,nub=0;
    int arr[100001]={0};
    int dp[100001]={0};
    
    scanf("%d",&n);
    
    for(i = 0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    dp[0] = 0;
    for(i = 0 ;i < n;i++)
    {
        if(maxnum < i )
        {
            sub = -1;
            break;
        }
        maxnum =  max(maxnum,arr[i]+i);
       
        if(i == nub)
        {
            nub = max(nub,maxnum);
            if(i < n-1) sub++;
        }
        /*
        for(j = i-1; j >= 0 ;j-- )
        {
            if(arr[j]+j >= i)
            {
                nub = j;
            }
        }
        if(i > 0)
            dp[i] = min(dp[nub]+1,dp[i-1]+1);
        */
    }
    
        printf("%d",sub);
   return 0;
}

C++ 解法, 执行用时: 14ms, 内存消耗: 1228KB, 提交时间: 2022-07-21

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << "-1\n";
        return 0;
    }
    int nums[n];
    for (int i = 0; i < n; ++i) 
        cin >> nums[i];
    int maxi = 0, j = 0, steps = 0;
    for (int i = 0; i <= j; ++i) { // 当前可达j
        if (j >= n - 1) { // 当前可达末尾
            cout << steps << "\n";
            return 0;
        }
        maxi = max(maxi, i + nums[i]);
        if (i == j) {
            j = maxi; // 更新下一跳为当前最远位置
            ++steps;            
        }
    }
    cout << "-1\n";
    return 0;
}