A7927.兔子数列 递推题解

1.确定状态

这里最优状态为fib[n]，那么推到此状态的状态就是fib[i]

int fib[50];

2.确定边界

斐波那契数列的1、2项为1，此为边界

fib[1]=1;
fib[2]=1;

3.确定状态转移方程

这里每个状态是由它的前面两个相加得到的，所以：

fib[i]=fib[i-1]+fib[i-2];

4.完整代码

#include<iostream>
using namespace std;
int fib[100],n;
int main()
{
    fib[1]=fib[2]=1;
    cin>>n;
    for(int i=3;i<=n;i++)
    {
        fib[i]=fib[i-1]+fib[i-2];
    }
    cout<<fib[n];
    return 0;
}