数楼梯

题目描述

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

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

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

1
4

样例输出 #1

1
5

提示

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

代码

解法一：高精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a[5003][5003];//用二维数组，因为i表示第几个数，j表示那个数的值
//这是高精度加法通用写法
int len = 1;
void add(int m) {

	int c = 0;//表示进位
	for (int i = 1; i <= len; i++)
	{
		a[m][i] += a[m - 1][i] + a[m - 2][i] + c;
		c = a[m][i] / 10;
		a[m][i] = a[m][i] % 10;
		if (c > 0)
		{
			len++;
		}
	}

	while (len > 0 && a[m][len] == 0)//去除前导零
	{
		len--;
	}
}
int main() {
	int n;
	cin >> n;
	//初始化两个值
	a[1][1] = 1;
	a[2][1] = 2;
	for (int i = 3; i <= n; i++)
	{
		add(i);
	}
	//反向输出值
	for (int i = len; i >= 1; i--)
	{
		cout << a[n][i];
	}
	return 0;
}