走楼梯

走楼梯

题目描述

楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。

输入描述

一个数字，楼梯数。

输出描述

输出走的方式总数。

样例输入 1

4

样例输出 1

5

代码

递归

#include<stdio.h>

int step(int n){
    if(n == 1 || n == 2){
        return n;
    }else{
        return step(n-1) + step(n-2);
    }
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d",step(n));
    return 0;
}

这题没多少印象，但是印象里递归好像有测试点过不去，会超时，再补一个动态规划的题解。

动态规划

#include<stdio.h>


int main(){
    int n;
    scanf("%d",&n);
    int res[n+1];
    res[0] = 0;
    res[1] = 1;
    res[2] = 2;
    if(n<=3)
    {
        printf("%d",n);
        return 0;
    }
    for(int i=3;i<=n;i++)
    {
        res[i]=res[i-1]+res[i-2];
    }
    printf("%d",res[n]);
    return 0;
}