问题描述

思路

这个递推公式并不难，n阶台阶的走法数目即为n-1阶的走法数目（再走一节就到了）加上n-2阶的走法数目。
当看到部分测试样例WA，而且都是靠后的测试样例而不是随机分散，那么有很大几率是数据类型存储有问题，存不了太大的数，而不是递推公式的问题。
想这题一样，当输入的N为500时，结果为：

。。。
就这样吧。。不搞竞赛的话应该也用不上

#include<bits/stdc++.h>
using namespace std;
long long countStairs(int N){
	if(N == 1){
		return 1;
	}
	if(N == 2){
		return 2;
	}
	
	vector<long long> dp(N+1, 0);
	dp[1] = 1;
	dp[2] = 2;
	for(int i = 3; i <= N; i++){
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[N];
}
int main(){
	int N;
	cin>>N;
	cout<<countStairs(N);
	return 0;
}