问题描述
思路
这个递推公式并不难,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;
}
标签:return,走法,int,高精度,样例,long,力扣,楼梯,dp
From: https://www.cnblogs.com/satsuki26681534/p/18067340