2022年9月7号顺丰科技大数据和数据分析工程师笔试题
题目是求以下递归的函数调用次数 F ( n ) = { 1 n < = 3 f ( n − 1 ) + f ( n − 2 ) + f ( n − 3 ) n > 3 F(n) =\left\{ \begin{aligned} 1 & & n3 \\ \end{aligned} \right. F(n)={1f(n−1)+f(n−2)+f(n−3)n3 输出一行，包含一个整数，表示在求F( n )过程中，F函数被调用的总次数。不必考虑计算过程中产生的数字溢出等问题。由于答案可能很大，故输出答案对1000000007取模所得值即可。
2 解析动态规划，来做，有这种重复计算，涉及备忘录，那就考虑dp。 状态：数值F(n)的递归次数 装填转移： d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] + d p [ i − 3 ] + 1 , i > 3 dp[i] = dp[i-1]+dp[i-2]+dp[i-3]+1 ,i>3 dp[i]=dp[i−1]+dp[i−2]+dp[i−3]+1,i>3
3 python 实现def func(n):
dp = [0]*n
dp[0] = 1
dp[1] = 1
dp[2] = 1
for i in range(3,n):
dp[i] =dp[i-1]+dp[i-2]+dp[i-3]+1
return dp[n-1]
n = 2000
count = func(n)
print(count%(1e9+7))
