京东笔试数据分析讨论
第一题股票AC27%就不谈了,第二题简单些,想跟牛友讨论一下,
贴一下原题(第二题):
作者:十四颗糖来源:牛客网#一共有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
这个题是个简单的递归,但是只AC了78%,有些case我没考虑到,现在复盘还是没想出来,贴一下Python代码。讨论一下我哪些情况没有考虑。
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)