SYC最近做了一道题目,题目是这样的:
小明一次可以迈上不多于三级台阶,小明现在想知道走到第n级台阶有多少种走法.
这是一道基础的动态规划题目,但是愚蠢的SYC并不会使用dp(动态规划)算法,只好使用递归的方法来求解,不出意外,因为复杂度太大,代码运行超时了,SYC现在想知道到底输入n后到底递归调用了多少次solve()函数,solve()函数如下:
int solve(int n)
{
if(n==1)
return 1;
else if(n==2)
return 2;
else if(n==3)
return 4;
else
return solve(n-1) + solve(n-2) + solve(n-3);
}
输出结果过大,对1,000,000取模.
输入一个整数n, n<=100,000,000
输出solve函数调用的次数,答案对1,000,000取模.