【晴问算法】提高篇—动态规划专题—斐波那契数列II
题目描述
给定正整数n，求斐波那契数列的第n项F(n)。
令F(n)表示斐波那契数列的第n项，它的定义是:
当n=1时，F(n)=1;
当n =2时，F(n)=1;
当n>2时，F(n)=F(n-1)+F(n-2)。
输入描述
一个正整数n(1≤n≤10^4)
输出描述
斐波那契数列的第n项F(n)。
由于结果可能很大，因此将结果对10007取模后输出。
输入
1
输出
1
解释
边界定义：边界定义:F(1)=1
样例2
输入
3
输出
2
解释
F(3)=F(2)+F(1)=1+1=2
#include <cstdio>
const int MOD = 10007;
const int MAXN = 10000 + 1;
int fib[MAXN];
int main() {
int n;
scanf("%d", &n);
fib[1] = fib[2] = 1;
for (int i = 3; i <= n; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
printf("%d", fib[n]);
return 0;
}这段代码是一个计算斐波那契数列第n项的程序。首先，它定义了MOD为10007，MAXN为10001，然后声明了一个长度为MAXN的整型数组fib用来存储斐波那契数列的值。
在主函数main()中，程序首先读取输入的n值，然后初始化fib数组的前两个元素为1。接下来通过一个循环计算出斐波那契数列从第3项到第n项的值，并且对每个计算结果取模MOD。最后，输出第n项的斐波那契数列的值。