已知斐波那契数列 Fn =Fn−1+Fn−2 (n>=3), F1=1,F2=1求解该数列的第n项,结果对998244353取模。
输入格式:
输入一个正整数n (1<=n<=10000000)。
输出格式:
输出一个数,数列的第n项
输入样例1:
1
输出样例1:
1
输入样例2:
3
输出样例2:
2
思路: 我刚开始用的普通递归但有一个测试点过不了,出现的问题就是,因为递归不停反复运算导致数据量太大。后来考虑了优化递归就是开一维数组保存了递归结果,但是还是处理不了太大的数据,测试点5无法通过。
普通递归代码:
1 2 3 4 5
| int Fib(int n) { if(n == 1 || n == 2) return 1; else return Fib(n-1) % 998244353 + Fib(n-2) % 998244353; }
|
初步优化递归代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include <iostream> #include <cstdio> #include <memory.h> using namespace std; const int maxn = 10000000; int dp[maxn]; int fib(int n) { if( n == 1 || n == 2) return 1; if( dp[n] != -1) return dp[n]; else { dp[n] = (fib(n-1) + fib(n-2))% 998244353; return dp[n]; } } int main() { memset(dp, -1, sizeof(dp)); int n; cin >> n; cout << fib(n) ; return 0; }
|
最终解决办法:
可能这道题不适合递归,于是采用的动态规划递推写法,从底向上同时开一个一维数组F,用来记录保存已经计算过的结果,就可以避免下次遇到相同的子问题时的重复计算。
注意点: F[i] = (F[i-1] + F[i-2]) % mod
不等于F[i] = F[i-1] % mod+ F[i-2])% mod
;比如当和正好为mod的倍数时候第一个式子结果为0,第二个为mod。
AC代码:
动态规划自底向上递推:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include <iostream> #include <cstdio> using namespace std; const int maxn = 10000000; int F[maxn]; int fib(int n) { if(n == 1 || n == 2) return 1; else { F[1] = 1; F[2] = 1; for(int i = 3; i <= n ; i++) { F[i] = (F[i-1] + F[i-2]) % 998244353; } return F[n]; } } int main() { int n; cin >> n; cout << fib(n) ; return 0; }
|