算法题：走楼梯(stairs)

问题描述

楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？

输入格式

台阶数

输出格式

走法数量

样例

输入

500

输出

225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626

数据范围

解决方案

思路

递推+高精度运算

代码

#include <iostream>

using namespace std;

int arr[5000][5000];

int main() {

    int n;
    cin >> n;

    arr[1][0] = 1;
    arr[2][0] = 2;
    for (int i = 3; i <= n; ++i) {
        for (int j = 0; j < 5000; ++j) {
            int temp = arr[i][j] + arr[i - 1][j] + arr[i - 2][j];
            arr[i][j] = temp % 10;
            arr[i][j + 1] = temp / 10;
        }
    }

    int i = 4999;
    for (; i >= 0; --i) {
        if (arr[n][i] != 0)
            break;
    }

    for (; i >= 0; --i) {
        cout << arr[n][i];
    }

    return 0;
}