Fibonacci--动态规划_21、求递归关系fn=fn-1+fn-2 (n≥2),f0=1,f1=1的通项

题目一来源：codeup链接

题目描述
The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55…} are defined by the recurrence:
F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2
Write a program to calculate the Fibonacci Numbers.

输入
Each case contains a number n and you are expected to calculate Fn.(0<=n<=30) 。

输出
For each case, print a number Fn on a separate line,which means the nth Fibonacci Number.

样例输入
1
样例输出
1

1. 递归写法[记忆化搜索]

#include <iostream>
using namespace std;
const int maxn = 32;
int dp[maxn];
int n;
int fib(int n)
{
    if (n == 1 || n == 0)
    {
        return n;
    }
    if (dp[n] >= 0)
    {
        return dp[n];
    }
    return fib(n - 1) + fib(n - 2);
}
int main()
{
    while (cin >> n)
    {
        for (int i = 0; i <= n; i++)
        {
            dp[i] = -1;
        }
        cout << fib(n) << endl;
    }
    return 0;
}
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
27
28
29

2. 递推写法

#include <iostream>
using namespace std;
const int maxn = 32;
int dp[maxn];
int n;
int fib(int n)
{
    if (dp[n] >= 0)
    {
        return dp[n];
    }
    dp[0] = 0;
    dp[1] = 1;
    for(int i=2;i<=n;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
int main()
{
    while (cin >> n)
    {
        for (int i = 0; i <= n; i++)
        {
            dp[i] = -1;
        }
        cout << fib(n) << endl;
    }
    return 0;
}
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
27
28
29
30

题目二来源：百练2758
描述
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 1000000)。
输出
n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到的结果。

样例输入
4
5
2
19
1
样例输出
5
1
181
1

#include <iostream>
using namespace std;
const int maxn = 1e6+10;
int dp[maxn];
int n;
int fib(int n)
{
    if (dp[n] >= 0)
    {
        return dp[n];
    }
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2])%1000; //要在这里进行取模运算，否则会报错
    }
    return dp[n];
}
int main()
{
    int t;
    cin >> t;
    for (int i = 0; i <= maxn; i++)
    {
        dp[i] = -1;
    }
    fib(maxn);
    while (t--)
    {
        cin >> n;
        cout << dp[n]<< endl;
    }
    return 0;
}
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
27
28
29
30
31
32
33
34
35