【暑期每日一题】洛谷 P1255 数楼梯

题目链接：P1255 数楼梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

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

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

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

- 对于 60% 的数据，N <= 50；   
- 对于 100% 的数据，1 <= N <= 5000。

AC code:

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

string f(string a,string b)
{
	if(a=="0" && b=="0")
	{
		return "0";
	}
	int t1=a.size();
	int t2=b.size();
	int n=abs(t1-t2);
	
	for(int i=0;i<n;i++)
	{
		if(t1>t2)
			b="0"+b;
		else
			a="0"+a;
	}
	string s; // 和 
	int c=0; // 进位
	int d=0; // 低位 
	int len=a.size()-1;
	for(int i=len;i>=0;i--)
	{
		d=(a[i]-'0'+b[i]-'0')%10+c;
		if(d==10)
		{
			c=1;
			s="0"+s;
			continue;
		}
		s=to_string(d)+s;
		c=(a[i]-'0'+b[i]-'0')/10;
		if(c==1 && i==0)
			s="1"+s;
	}
	if(s[0]=='0')
		s="1"+s;
	return s;
}

int main()
{
	vector<string> a(1);
	a.push_back("1");
	a.push_back("2");
	for(int i=3;i<=5000;i++)
	{
		string t=f(a[i-2],a[i-1]);
		a.push_back(t);
	}
	int n;
	cin>>n;
	cout<<a[n];
	
	return 0;
}