NC24665. 递归函数的次数
描述
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取模.
示例1
输入:
1
输出:
1
示例2
输入:
2
输出:
1
示例3
输入:
3
输出:
1
说明:
(只调用了一次solve()函数,既solve(3))示例4
输入:
5
输出:
7
说明:
(调用了一次solve(5),一次solve(4),两次solve(3),两次solve(2),一次solve(1),共七次solve()函数)C++(clang++ 11.0.1) 解法, 执行用时: 386ms, 内存消耗: 436K, 提交时间: 2023-04-12 19:09:35
#include<bits/stdc++.h>
using namespace std;
int ans=0,a1,a2,a3;
int main()
{
int n,num;
cin>>n;
a1=1;a2=1;a3=1;
if(n<=3)
{
ans=1;
}else
{
for(int i=4;i<=n;i++)
{
ans=a1+a2+a3+1;
ans%=1000000;
a1=a2;
a2=a3;
a3=ans;
}
}
cout<<ans;
}