3. 台阶问题

数楼梯

题目描述

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

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

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

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

---

解题思路：递推+高精度

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
const int N = 100010;vector<vector<int>>a(5010);vector<int> add(vector<int>A,vector<int>B)
{if(A.size()<B.size())return add(B,A);int t=0; vector<int>sum;for(int i=0;i<a.size();i++){t+=A[i];if(i<B.size())t+=B[i];sum.push_back(t%10);t=t/10;}if(t)sum.push_back(t);return sum;
}vector<int> solve(int n)
{a[1]={1}; a[2]={2};for(int i=3;i<=n;i++){a[i]=add(a[i-1],a[i-2]);}return a[n];
}int main()
{int n; cin>>n;vector<int>ans=solve(n);for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];return 0;
}

---

本题使用的模板：高精度加法

vector<int> add(vector<int> &A, vector<int> &B)  // C = A + B, A >= 0, B >= 0
{if (A.size() < B.size()) return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i ++ ){t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}