好像这个算法看看就没啥好说了,具体输入数据与获取结果分开处理可以这样~

#include<stdio.h>

unsigned fun( const size_t [],size_t );

int main( void )
{
    #define __ARR_LEN( s )    \
        (sizeof (s)/sizeof (*s))
        
    const size_t a[][5]=
    {
        {2,3,1,1,4},
        {3,2,1,0,4},
        {3,3,1,0,4},
        {3,0,0,0,4}
    };
    
    size_t i;
    
    for (i=0;i!=__ARR_LEN(a);++i)
        printf("%u\n",fun(a[i],__ARR_LEN(*a)));
    
    return 0;
    
    #undef __ARR_LEN
}


 unsigned fun( const size_t a[],size_t len )
{
    size_t i;
    size_t k;
    
    for (i=k=0;i!=len;++i)
    {
        if (k<i+a[i]&&k>=i)
            k=i+a[i];
        else if (k<i)
            return 0;
        
        if (i+a[i]>=len-1)
            return 1;
    }
    
    return 0;
}

当然还可以从第k个元素开始回溯遍历~大意就是说从k开始遍历回来,如果遍历结果小于当前MAX则返回前一个元素,这个明显适合用dfs实现,这样在有解的情况下跳过遍历的元素可以尽可能多~

[此贴子已经被作者于2018-4-11 17:28编辑过]

默认5个数
for(i=0;i<4&&a[i]!=0;i+=a[i]);
    if(i==4)
        printf("true");
    else
        printf("fasle");

[此贴子已经被作者于2018-4-11 19:45编辑过]

用dfs深度搜索还可以这样,检索时可以跳过尽量多的元素,当然执行次数最多的情况还是要完全遍历的~

PS:然后发现这个优化方面逻辑有bug,其实遍历时间复杂度最大还是o(n^2),不过意思到了算是这样了~

#include<stdio.h>

unsigned fun( const size_t[],size_t );

static unsigned _fun(const size_t [],size_t,size_t*,size_t );

int main( void )
{
    #define __ARR_LEN( s )    \
        (sizeof (s)/sizeof (*s))
        
    const size_t a[][5]=
    {
        {1,3,1,1,4},
        {3,2,1,0,4},
        {3,3,1,0,4},
        {3,0,0,0,4}
    };
    
     size_t i;
    
    for (i=0;i!=__ARR_LEN(a);++i)
        printf("%u\n",fun(a[i],__ARR_LEN(*a)));
    
    return 0;
    
    #undef __ARR_LEN
}

unsigned fun( const size_t a[],size_t len )
{
    size_t _max=a[0];
    
    _fun(a,0,&_max,len);
}

static unsigned _fun(const size_t a[],size_t k,size_t* _max,size_t len )
{
    size_t i;
    
    if (*_max>=len-1)
        return 1;
    
    for (i=k+a[k];i!=k;--i)
    {
        if (i+a[i]>*_max)
        {
            *_max=i+a[i];
            
            _fun(a,i,_max,len);
        }
        else
            continue;
        
        if (*_max>=len-1)
            return 1;
    }
            
    return 0;
}

[此贴子已经被作者于2018-4-11 22:04编辑过]

然后修正了13楼的优化逻辑上的bug,这样差不多就可以保证每个元素最多遍历一次了~可以看看~

#include<stdio.h>

unsigned fun( const size_t[],size_t );

static unsigned _fun(const size_t [],size_t,size_t,size_t*,size_t );

int main( void )
{
    #define __ARR_LEN( s )    \
        (sizeof (s)/sizeof (*s))
        
    const size_t a[][5]=
    {
        {1,3,1,1,4},
        {3,2,1,0,4},
        {3,6,1,0,4},
        {3,0,0,0,4}
    };
    
     size_t i;
    
    for (i=0;i!=__ARR_LEN(a);++i)
        printf("%u\n",fun(a[i],__ARR_LEN(*a)));
    
    return 0;
    
    #undef __ARR_LEN
}

unsigned fun( const size_t a[],size_t len )
{
    size_t _max=a[0];
    
    _fun(a,0,0,&_max,len);
}

static unsigned _fun(const size_t a[],size_t i,size_t mark,size_t* _max,size_t len )
{
    if (*_max>=len-1)
        return 1;
        
    for (i+=a[i];i!=mark;--i)
    {
        if (i+a[i]>*_max)
            _fun(a,i,*_max=i+a[i],_max,len);
        else
            continue;
            
        if (*_max>=len-1)
            return 1;
    }
            
    return 0;
}

[此贴子已经被作者于2018-4-11 22:00编辑过]

所以老哥你可以选择性的加点注释，毕竟代码不是给自己看的

所以老哥你可以选择性的加点注释，毕竟代码不是给自己看的

刚刚那个发现问题先编辑掉了或者我可以在代码之外说明一下~

解释我不怎么会,不过我知道具体过程怎么说,看图就可以了~

这里有个抽象数组~


首先从下标0开始检索取其值跳转到(1)
然后回溯找到可以更新的最大值(2),跳转到(3)
然后(3)回溯到(1)也找不到最大值那就退出本次递归由(4)跳转到(5)
再从上一层递归开始回溯到(6)找到可更新的最大值并跳转到(7)
最后回溯找到可更新的最大值(8)跳转到终点(9)

这样可以尽量少地检索元素,当然要从当前最大值开始回溯到原点才知道有没有新的可更新的最大值~

然后再补充说明一下,其实11楼的代码和13楼的代码某种程度上是等价的,因为执行效率和具体输入数据直接相关~

如果输入数据取值前面遇到某个极大值能够直接跳跃到终点,那11楼的遍历元素会相对来说少一点,当然如果数据分布较为均匀彼此之间对最大值影响不大,并且取决于能跳到最后一个下标元素偏向数组的后半部分,那13楼的代码遍历的元素会少一点,所以简单来说其实两种方法效率都和数据的取值分布直接相关,如果是对人为输入的极端数据进行处理那就要看具体情况了~