跳跃游戏（一）

yyy-a / 2023-05-29 / 原文

描述

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置，则输出true，否则输出false。

数据范围:

输入描述：

第一行输入一个正整数 n ，表示数组 nums 的长度

第二行输入 n 个整数表示数组的每个元素

输出描述：

输出 true 或者 false

思路一（会超时）

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5+10;
int a[N];
bool dp[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[1]=true;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(dp[i-j]&&a[i-j]>=j)
            {
                // cout<<"i="<<i<<endl;
                dp[i]=true;
                break;
            }
        }
    }
    if(dp[n]) cout<<"true"<<endl;
    else cout<<"false"<<endl;
}

　　思路二：

从i=1开始依次遍历每一层所能到达的最高层，标识符high表示目前能到达的最高层，如果high小于i则表示到达不了第i层返回false

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5+10;
int a[N];
bool dp[N];
int main()
{
    int high = 1;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(high>=n)
        {
            cout<<"true"<<endl;
            break;
        }
        if(i<=high)
        {
            high=max(high,i+a[i]);
            // cout<<"high="<<high<<endl;
        }
        else
        {
            cout<<"false"<<endl;
            break;
        }
    }
}