数楼梯
题目描述
楼梯有 $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;
}