数楼梯题解

题目描述

楼梯有N阶，上楼可以一步上一阶，也可以一步上两阶。那么走到第N阶楼梯共有多少种不同的走法呢？

输入格式:
一个正整数 N（1<=N<=5000），表示楼梯阶数。

输出格式:
输出一个数，表示走到第N阶楼梯有多少种走法。
注意，数据范围很大，即使是64位也可能不够存。

解题思路

1.建立一个二维数组，由低位到高位逆序存储斐波那契数列
2.递归得到斐波那契数列：结合高精度加法，注意进位和位数
3.反向输出斐波那契数列

完整代码

#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
    int n, i, j, count = 1, t;
    static char ans[5200][2000];
    scanf("%d", &n);
    ans[1][1] = 1;
    ans[2][1] = 2;
    if (n <= 2) {
        printf("%d", ans[n][0]);
    }
    else {
        for (i = 3; i <= n; i++) {
            t = count;
            for (j = 1; j <= t; j++) {
                ans[i][j] += ans[i - 1][j] + ans[i - 2][j];
                ans[i][j + 1] += ans[i][j] / 10;
                ans[i][j] %= 10;
                if (ans[i][t + 1] > 0) {
                    count++;
                }
            }
        }
        for (i = count; i >= 1; i--) {
            printf("%d", ans[n][i]);
        }
    }
    return 0;
}

数楼梯题解

原文：https://www.cnblogs.com/dump16/p/12498580.html