原题链接： https://www.luogu.com.cn/problem/P1255

这题按理来说是非常简单的递归就能完事的但是一看这数据就明白那么简单，得用高精度加法(递归是没法使用高精度加法 的)而一牵扯到高精度加法就非常的蛋疼，但是这一题虽然是水题但是对于我这种菜鸡选手来说，其中还是有比较多的 代码细节值得学习的

这一题列出来一下两个做法

递推式做法是没有用dp的状态转移方程(其实没有那么高大上就是递推式)
斐波那契的递推式，由此可以得出DP的状态转移方程：

F(1)=1 , F(2)=2 , F(n)=F(n-1)+F(n-2)
而是用到的求斐波那契数列的滚动数组法
(两种代码其中高精度加法的核心代码是一样的)

递归做法(TLE)

#include<iostream>
using namespace std;
int F(int n){
    if(n==1)return 1;
    if(n==2)return 2;
    return F(n-1)+F(n-2);
}
int main(){
    int n;
    cin>>n;
    cout<<F(n)<<endl;
    return 0;
} 

高精度代码的核心代码如下

不管是两种代码的那种代码其实高高精度的加法的实现代码的思想
是一样的就是先用两个数的每个位数相加不管过没过10都先储存在
数组里面，之后再判断每个数的进位问题然后以此类推到所求的N
阶的方案数

void jiafa(int k)//高精度加法
{
    for(int i = 1; i <= len; i ++)//两数相加
        f[k][i] = f[k - 1][i] + f[k - 2][i];

    for(int i = 1; i <= len; i ++)//进位
    if(f[k][i] >= 10)
    {
        f[k][i + 1] += f[k][i] / 10;
        f[k][i] %= 10;
        if(f[k][len + 1] > 0) 
        len ++; 
    }

}

滚动数组法

#include<iostream>

using namespace std;

int a[5000], b[5000], c[5000];
int n;
int main()
{   
    int x = 1;//x表示当前的最大位数
    cin >> n;

    if(n < 3)
    {
        cout << n;
        return 0;
    } 

    a[1] = 1, b[1] = 2;
    for(int i = 3; i <= n; i ++)
    {   
        for(int j = 1; j <= x; j ++)
            c[j] = a[j] + b[j];

        for(int j = 1; j <= x; j ++)
        {
            if(c[j] > 9)
            {
                c[j + 1] += c[j] / 10;
                c[j] %= 10;
                if(j + 1 > x)
                x ++;
            }
        }

    for(int i = 1; i <= x; i ++)
        a[i] = b[i];
    for(int i = 1; i <= x; i ++)
        b[i] = c[i];
    }   
    for(int i = x; i >= 1; i --)
    cout << b[i];

    return 0;
}

递推式法(dp状态转移方程)

f[5010][5010]数组的第一维是总的N的台阶数，第二位是每个方案数的每一位数

#include<iostream>

using namespace std;

int n, len;
int f[5010][5010];

void jiafa(int k)//高精度加法
{
    for(int i = 1; i <= len; i ++)//两数相加
        f[k][i] = f[k - 1][i] + f[k - 2][i];

    for(int i = 1; i <= len; i ++)//进位
    if(f[k][i] >= 10)
    {
        f[k][i + 1] += f[k][i] / 10;
        f[k][i] %= 10;
        if(f[k][len + 1] > 0) 
        len ++; 
    }

}

int main()
{
    cin >> n;
    len = 1;
    f[1][1] = 1;//预处理
    f[2][1] = 2;//预处理
    for(int i = 3; i <= n; i ++)//开始计算 
        jiafa(i);
        for(int i = len; i >= 1; i --)//倒序输出
        cout << f[n][i];
        return 0;

}