数楼梯

题目描述

楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入输出格式

输入格式：

 

一个数字，楼梯数。

 

输出格式：

 

走的方式几种。

 

输入输出样例

输入样例

4

输出样例

5

说明

用递归会太慢，需用递推

（60% N<=50 ,100% N<=5000)

---

思路：

方法一: 数组模拟

最基本的做法，但缺陷也很明显，就是太耗空间，如果遇见一些独流，这就行不通了，但本题还是OK的

代码：

#include<stdio.h>
int n,len=1,f[5001][5001];

void hp(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]) len++;
        }
    }
}

int main()
{
    scanf("%d",&n);
    f[1][1]=1,f[2][1]=2;
    for(int i=3;i<=n;++i) hp(i); 
    for(int i=len;i>=1;--i)
        printf("%d",f[n][i]);
    return 0;
}