用递归会超时,改用动态规划,数组保存计算结果,避免重复计算
#include <iostream>
using namespace std;
int dp[10010];
long long Fibonacci(int n){
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; ++i){
dp[i] = (dp[i-1] + dp[i-2]) % 999983;
}
return dp[n];
}
int main() {
int n;
cin >> n;
cout << Fibonacci(n);
return 0;
}