【Leetcode刷题Python】高效求递归中函数的调用次数(动态规划方法，顺丰笔试题)

2022年9月7号顺丰科技大数据和数据分析工程师笔试题

题目

是求以下递归的函数调用次数
F ( n ) = { 1 n < = 3 f ( n − 1 ) + f ( n − 2 ) + f ( n − 3 ) n > 3 F(n) =\left\{ 1n<=3f(n−1)+f(n−2)+f(n−3)n>3

\right. F(n)={1f(n−1)+f(n−2)+f(n−3)​​n<=3n>3​
输出一行，包含一个整数，表示在求F( n )过程中，F函数被调用的总次数。不必考虑计算过程中产生的数字溢出等问题。由于答案可能很大，故输出答案对1000000007取模所得值即可。

2 解析

动态规划，来做，有这种重复计算，涉及备忘录，那就考虑dp。
状态：数值F(n)的递归次数
装填转移：
$$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))
1
2
3
4
5
6
7
8
9
10
11
12