HBC24665[NOI2018]多边形,插头dp,动态规划递归函数的次数题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

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

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取模.

标签： HBC24665[NOI2018]多边形 插头dp 动态规划递归函数的次数题解