洛谷 P1255 数楼梯
题目描述
楼梯有 NN 阶，上楼可以一步上一阶，也可以一步上二阶。 编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
输入输出样例
输入 #1
4输出 #1
5很简单的高精+斐波那契
用一个二维数组就解决了
大概就是用二维数组 f 来存储走k个阶梯所用的步数
最后循环输出
话不多说，上代码！
#include<bits/stdc++.h>
using namespace std;
int n,f[5010][5010],s=1; //二维数组别开太大，小心TLE找上门
void staircase(int k) //至于为什么叫staircase（太阳也不知道...）
{
for(int i=1;i<=s;i++)
{
f[k][i]=f[k-1][i]+f[k-2][i]; //公式应该不用多说吧
}
for(int i=1;i<=s;i++) //处理进位
{
if(f[k][i]>=10)
{
f[k][i+1]+=f[k][i]/10;
f[k][i]=f[k][i]%10;
if(f[k][s+1])
{
s++;
}
}
}
}
int main()
{
cin>>n;
f[1][1]=1,f[2][1]=2;
for(int i=3;i<=n;i++) //从3开始以免越界
{
staircase(i); //其实 “staircase”是楼梯的英文
}
for(int i=s;i>=1;i--) //这里要注意是逆序输出，为什么是逆序输出应该不用多讲吧...
{
cout<<f[n][i];
}
return 0;
}
？
//这个问号会使复制题解的人AC不了