题目描述

使用递归的方式求斐波那契数列的第n项。

斐波那契数列：1,1,2,3,5…，这个数列从第3项开始，每一项都等于前两项之和

输入格式
共一行，包含整数n

输出格式
共一行，包含一个整数，表示斐波那契数列的第n项。

数据范围
1≤n≤30

样例

输入样例：
4
输出样例：
3

算法1

简单题 自用笔记记录
动态规划和递归的入门样例题

斐波那契数组的属性就是状态转移方程
arr[0] = 1;
arr[1] = 1;
arr[i] = arr[i-1]+arr[i-2];

C++ 代码

#include <iostream>


using namespace std;

const int N =30+10;

int n;

int arr[N];

int main()
{
    cin>>n;

    arr[0] = 1;
    arr[1] = 1;

    for(int i =2;i<N;i++){
        arr[i] = arr[i-1]+arr[i-2];
    }

    cout <<  arr[n-1]<< endl;

    return 0;
}