數樓梯

題目描述

樓梯有 $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;
}