学递归递推的孩子们碰壁了？（猜你肯定没注意到标签中的 高精度 ）

首先，学递归你肯定学过 斐波那契数列‌ ,这道题就是 ... 嗯嗯，对，只是包装了一下，说直白点，ze TM 就是啊！（哦齁齁齁齁齁！）

没学过？（先去学了再来做这道题吧）

---

这道题输入5000，答案是：627630280048895708603525310...70626
满打满算总共1245位数（这你敢不用高精度？）

（现在看看本题解代码，觉得简单看楼上 详情请看此题解：楼上的题解 矩阵快速幂）

---

说那么多废话，接下来进入我的思路 （啥子思路，可以不看）
一开始我注意到了这道题的范围，点开了算法标签——好家伙，果真是高精度！
这里我运用递推的方式，我的代码主要部分其实就是记忆化思想，

for(int i=3;i<=n;i++){
    a[i]=a[i-1]+a[i-2];
}
cout<<a[n];

没错，a[i-1]代表前面第一个楼梯到达方式个数，a[i-2]代表前面第二个楼梯到达方式个数，a[i]代表本级台阶到达方式个数
很显然，1245位数，long long也存不下。
好消息，高精度...废话，高精度本身就可以

高精度引入

由于空间问题，我们在处理一些大数运算时就连常用的long long也变得招笑：区区64位数，存的下我1245位数？简直就是 区 一般的存在。于是，聪明的入类想出了一个巧妙的算法——高精度！高精度简单来说就是用一个数组来存一个数。这听起来是不是很意外？一个数组这么大的空间，来存那么小一个数？实则不然，用这个数组存的数可以到达百位数，甚至是千位，万位，还能更高。他的便是将这个数个位存在这个数组的零号位，十位存在这个数组的一号位，以此类推。因此，数组开多大，这个数就可以有多少位数，甚至更多。

在小学。我们学习了一个古老的计算方式——竖式。没错，高精度的运算本质上就是竖式
加法就是从个位至最高位依次计算，并处理进位。同样的，高精度从数组中存储的最低位至最高位依次计算，并处理进位。
同理，减法就是从个位至最高位依次计算，并处理借位。同样的，高精度从数组中存储的最低位至最高位依次计算，并处理借位。
再同理...乘法除法亦是如此,这就是高精度的简单运算。
下面是完整代码，看完我的思路建议自己写一遍，不要着急抄。

#include <bits/stdc++.h>
using namespace std;
int a[5001][5000];                                                    //这里一共可以存5000位数的数字5001个，想想为什么: )
int len[10000];                                                         //这里存放的是这5001个数各自的长度
int n;
int main(){
	a[1][1]=1;                                                            //数据初始化
	len[1]=1;
	a[2][1]=2;
	len[2]=1;                                                             //存入n=1与n=2的情况其实只存n=1的情况也可以 
	int k=3;
		cin>>n;
		int lenm,tmp;                                                  //lenm表示第一个楼梯到达方式个数与第二个楼梯到达方式个数位数最高tmp表示进位 
		for(int i=3;i<=n;i++){                                     //主循环，算到n
			lenm=max(len[i-1],len[i-2]);                       //想想这一步在干什么？
			tmp=0;                                                       //进位初始化，算每一阶楼梯都要归零 
			for(int y=1;y<=lenm+1;y++){                   //从最低位开始往最高位算 
				a[i][y]=(a[i-1][y]+a[i-2][y]+tmp)%10;    //取余不能丢 
				tmp=(a[i-1][y]+a[i-2][y]+tmp)/10;        //判断进制
				if(a[i][lenm+1]){                                     //更新位数 （想想这个判断是干什么用的）
					len[i]=lenm+1;
				}else{
					len[i]=lenm;
				}
			}
		}
		for(int i=len[n];i>=1;i--){   //倒序输出（这一步必须要搞懂，为何不正序输出？仅仅是因为正序输出是错的吗？底层原理必须要搞懂）
			cout<<a[n][i];
		}
		cout<<'\n';
	return 0;
}

祝你今后在题目分析上更进一步，（看算法标签是一个方法，没有还不是要你自己分析啊喂！）