[数据结构与算法]洛谷题解-P1255数楼梯

题目概况

链接： https://www.luogu.com.cn/problem/P1255
难度： 普及-

题目分析

一道简单的 递推题
一次可以走一级或两级阶梯，（突然想起《少年班》这部电影里那个人拿着个乌龟壳就算出来了…）首先我们来推一下递推式：

0级阶梯：
零种

一、1级阶梯：

1
共一种

二、2级阶梯：

1 1
2
共两种

三、3级阶梯：

1 1 1
1 2
2 1
共三种

四、4级阶梯

1 1 1 1
1 1 2
1 2 1
2 1 1
2 2
共五种

继续：
然后大家再往下推，就可以发现这是斐波那契数列（fib），非常友好：

f[i] = f[i - 1] + f[i - 2]

定睛一看数据范围，N <= 5000??（要命） fib数列加到后面肯定溢出（long long类型加也只能50分），那肯定得用高精度加高精度运算了（不会超时，相信CPU，我最慢的也只有12ms）。另外为了递推方便f[0]设为1，遇到N=0就特判好了。
高精度加单精度运算不会戳这：https://blog.csdn.net/lightningcs/article/details/119542002

完整代码

#include<cstdlib>
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 5005;
int n;
string f[MAXN]; //开string类型存储
int a1[MAXN], a2[MAXN]; //高精运算用

string jiafa(string s1, string s2) {
	string ans;
	int len1 = s1.size();
	int len2 = s2.size();
	for (int i = 0; i < len1; i++) {
		a1[i] = s1[len1 - 1- i] - '0';
	}
	for (int i = 0; i < len2; i++) {
		a2[i] = s2[len2 - 1 - i] - '0';
	}
	
	len1 = max(len1, len2);
	for (int i = 0; i < len1; i++) {
		a1[i] += a2[i]; //加法
	}
	for (int i = 0; i < len1; i++) {
		a1[i + 1] += a1[i] / 10;
		a1[i] %= 10; //处理一下进位
	}
	while (a1[len1]) {
		a1[len1 + 1] += a1[len1] / 10;
		a1[len1] %= 10; //处理一下进位导致的长度增加
		len1++; 
	}
	for (int i = len1 - 1; i >= 0; i--) {
		ans += a1[i] + '0'; //累加到字符串上
	}
	return ans;
}

int main()
{
	cin >> n;
	f[0] = "1", f[1] = "1";
	if (n == 0) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 2; i <= n; i++) {
		f[i] = jiafa(f[i - 1], f[i - 2]); //高精度递推NB~！
	}

	cout << f[n] << endl;
	return 0;
}