祺哥刷题日记（五）数楼梯

题目 P1255 数楼梯

• 输入
4

• 输出
5


• 对于 60 % 60\% 的数据， N ≤ 50 N \leq 50
• 对于 100 % 100\% 的数据， N ≤ 5000 N \leq 5000

题解过程

1. 递归解法（超时）

#include

int stepUp(int num){
if(num == 1) return 1;
if(num == 0) return 0;
else return stepUp(num - 1) + 1 + stepUp(num - 2) + 1;
}

int main(){
int n;
scanf("%d", &n);
printf("%d", stepUp(n));
}


2. 递推法 （溢出）

#include

int main(){
int n;
long long step[3] = {1,2,3};
scanf("%d", &n);
if(n == 0 || n == 1 || n == 2) printf("%d", n);
else{
for(int i = 3; i < n; i++){
step[0] = step[1];
step[1] = step[2];
step[2] = step[0] + step[1];
}
printf("%lld", step[2]);
}
}


3. 递推+高精（AC）

#include
#include

using namespace std;

string res;
int lenA = a.size();
int lenB = b.size();

//补0
if(lenA < lenB){
for(int i = lenA; i < lenB; i++){
a = "0" + a;
}
}
else{
for(int i = lenB; i < lenA; i++){
b = "0" + a;
}
}

int len = max(lenA, lenB);
int c = 0;
int temp;
for(int i = len - 1; i >=0; i--){
temp = a[i] - '0' + b[i] - '0' + c;
c = temp / 10;
temp = temp % 10;
res = char(temp + '0') + res;
}
if(c != 0) res = char(c + '0') + res;
return res;
}

int main(){
int n;
string step[3] = {"1","2","3"};
scanf("%d", &n);
if(n == 0 || n == 1 || n == 2) printf("%d", n);
else{
for(int i = 3; i < n; i++){
step[0] = step[1];
step[1] = step[2];