京东笔试数据分析讨论

作者：十四颗糖

链接：https://www.nowcoder.com/discuss/411733?type=post&order=time&pos=&page=1

来源：牛客网

#一共有n个格子从左到右排成了一行，从1~n编号。第 i 个格子上写着一个正整数a[i]。

#一开始你在1号格子，并且手里有一个数字h0。

#当你在第 i 号格子，手里有数字 h 的时候，你有两个选择：

#（1）跳到第i + h号格子，手中的数字依然是h；

#（2）跳到第i + a[i]号格子，手中的数字变成a[i]；

#在跳跃的过程中是不允许超出n号格子的。

#你想知道一共有多少种不同的路径，可以从1号格子跳到n号格子，两条路径是不同的当且仅当它们经过的格子集合是不同的。输出不同路径的条数除以998244353的余数。

#输入

#第一行包含两个整数n和h0；

#第二行包含n个正整数a[i]；

#2 <= n <= 1000, 1 <= a[i], h0 <= n - 1

#样例输入

#5 1

#2 3 2 4 3

#样例输出

#4

#

#

#提示

#输入样例2

#3 10

#10 10 10

#

#输出样例2

#0

n, h0 = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = [-1] + a


def jump(idx, h):
    global n, a
    if idx == 0:
        return 
    if idx > n:
        return 0
    elif idx == n:
        return 1
    else:
        if h == a[idx]:
            return jump(idx + h, h)
        return (jump(idx + h, h) + jump(idx + a[idx], a[idx])) 


print(jump(1, h0) % 998244353)