Python递归地通过给定的索引跳转或更少跳转遍历列表，同时避免使用零

Question

我试图写一个只有一个参数的函数，一个正整数列表

它必须是递归的，并确定您是否可以从开始到结束，同时避免在0上着陆。它必须从第一个值list[0]开始，但您可以跳转全部或更少

比如说

list1 = [3,1,2,0,4,0,1]
list2 = [3,2,1,0,2,0,2]

列表1应该返回True，因为您可以从3跳到2，从4跳到1

列表2应该返回False，因为无论您如何跳转，您都将在第一个0处着陆

以下是我迄今为止的尝试：

def check_level(level):
    jump = level[0]
    if level[-1] == 0:
        return False
    elif jump == 0:
        return False
    
    elif jump == 0:
        return False
    
    elif len(level) > 1:
        if level[jump] > len(level):
            return True

        elif level[-1] == 0:
            return False
        
        elif level[0] != 0:
            if level[jump] == 0:
                level[0] -= 1
                return check_level(level)
            else:
                jump_index = level.index(level[jump])
                new_level = level[jump_index:]
                return check_level(new_level)

    else:
        return True

它不适用于所有示例，但对于其他示例，它会出现一个错误：

if level[jump] > len(level):
TypeError: '>' not supported between instances of 'list' and 'int'```

I am out of ideas on how to approach this and whether my approach is failed from the start... I hate recursion, hence I need to practice it.

Answer 1

在前进了许多位置之后，您只需与列表的其余部分一起递归即可。在从1到第一个元素值的距离内执行此操作，即完成：

def jumpable(A):
    if not A: return True # reaching end wins
    return any(jumpable(A[i+1:]) for i in range(A[0])) # try all distances

输出：

print(jumpable([3,1,2,0,4,0,1])) # True
print(jumpable([3,2,1,0,2,0,2])) # False

为了避免创建浪费内存的临时列表，您可以向下传递索引（而不是子列表），并将其用作下一级递归的起点：

def jumpable(A,i=0):
    if i>=len(A) : return True # reaching end 
    return any(jumpable(A,i+j+1) for j in range(A[i])) # try all distances

对于i=0的默认值，从外部调用函数时，仍然只有一个参数

Answer 2

一般逻辑是：

如果可以跳转到真实位置，则当前位置也是真实的

实施方式如下：

def checklevel(lst):
    if not lst:
        # no list is True (we are done)
        return True  
    return any( checklevel(lst[i:]) for i in range(1,lst[0]+1))

list1 = [3,1,2,0,4,0,1]
list2 = [3,2,1,0,2,0,2]

assert checklevel(list1)
assert not checklevel(list2)

请注意，对于大型列表，这是一个糟糕的解决方案，在这种情况下，您应该尝试使用迭代dp表