数楼梯

题目描述

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

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

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

• 对于 $60\%$ 的数据，$N \leq 50$；
• 对于 $100\%$ 的数据，$1 \le N \leq 5000$。

思路

f(x) = f(x - 1) + f(x - 2)
f(1) = 1；f(2) = 2
数据过大，long long不够大，必须上高精度。

AC代码

#include <iostream>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 10005;

long long n;
vector<int> mem[maxn];

vector<int> add(vector<int> v1, vector<int> v2)
{
   
    vector<int> v3;
    vector<int>::iterator it1 = v1.begin();
    vector<int>::iterator it2 = v2.begin();
    for (; it1 != v1.end() && it2 != v2.end(); it1++, it2++)
    {
   
        int sum = *it1 + *it2;
        v3.push_back(sum);
    }
    for (; it1 != v1.end(); it1++)
    {
   
        v3.push_back(*it1);
    }
    for (; it2 != v2.end(); it2++)
    {
   
        v3.push_back(*it2);
    }
    vector<int>::iterator it3 = v3.begin();
    int flg = 0;
    for (; it3 != v3.end(); it3++)
    {
   
        if (*it3 > 9)
        {
   
            *it3 -= 10;
            if (it3 + 1 == v3.end())
            {
   
                flg = 1;
            }
            else
            {
   
                *(it3 + 1) += 1;
            }
        }
    }
    if (flg)
    {
   
        v3.push_back(1);
    }
    return v3;
}

void printv(vector<int> v)
{
   
    vector<int>::reverse_iterator rit = v.rbegin();
    for (; rit != v.rend(); rit++)
    {
   
        cout << *rit;
    }
    cout << endl;
}

void f(long long x)
{
   
    if(!mem[x].empty()){
   
        return;
    }
    if (x < 3)
    {
   
        mem[x].push_back(x);
        return;
    }
    f(x - 1);
    f(x - 2);
    mem[x] = add(mem[x - 1], mem[x - 2]);
}

int main()
{
   
    cin >> n;
    f(n);
    printv(mem[n]);
    return 0;
}