问题标题: 酷町堂：2782 跳一跳

题目描述 Description

有n个盒子排成一行，每个盒子上面有一个数字a[i]，表示最多能向右跳a[i]个盒子；
小明站在左边第一个盒子，请问能否到达最右边的盒子？
比如说：[1, 2, 3, 0, 4] 可以到达第5个盒子；
[3, 2, 1, 0, 4] 无法到达第5个盒子。

输入描述 Input Description

多组测试数据
第一行，一个整数，n，表示n组测试数据
接下来n组
每组第一行一个整数，m，表示有m个盒子
接下来一行m个整数，x1 x2 … xi … xm，xi表示可以从第i个盒子上跳xi个盒子

输出描述 Output Description

对于每组测试数据，如果能跳到最后一个盒子，则输出1，否则输出0

 

本蒟蒻不知道用贪心怎么写，于是写了个dfs

可想而知，TLE60

#include<iostream>
#pragma GCC optimize(3)
using namespace std;
int n,t,a[105],flag;
void dfs(int pos){
    if(flag) return ;
    if(pos==n){
        flag=1;
        return ;
    }
    if(a[pos]==0) return ;
    for(int i=1;i<=a[pos];i++){
        if(pos+i<=n){
            dfs(pos+i);
        }
    }
}
int main(){
    cin>>t;
    while(t--){
        flag=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        dfs(1);
        cout<<flag<<endl;
    }
    return 0;
}

求正解思路