D1180 上台阶

AC_zzh2013 · 2024-01-30 16:59:39 · 个人记录

题目描述

楼梯有n阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，计算共有多少种不同的走法。

输入格式

输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。

输出格式

每一行输出对应一行输入的结果，即为走法的数目。

解题思路

先用递归解出剩余1、2和3阶，然后根据1、2、3阶的走法数，解出每一组测试数据的答案。

时间复杂度(n²）

核心代码

long long f(int x)//递归
{
    if (k[x]!=0)//第k阶台阶的种数不为0
    {
        return k[x];//返回第k阶台阶的种数
    }
   //前3个步数的总数
    if(x==1)
    {
        return 1;
    }    
}

完整代码

#include<bits/stdc++.h>
using namespace std;
long long k[100000];
long long f(int x)//递归
{
    if (k[x]!=0)//第k阶台阶的种数不为0
    {
        return k[x];//返回第k阶台阶的种数
    }
   //前3个步数的总数
    if(x==1)
    {
        return 1;
    }
    if(x==2)
    {
        return 2;
    }
    if(x==3)
    {
        return 4;
    }
    return k[x]=f(x-1)+f(x-2)+f(x-3);//最后返回步数的总数
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0)
        {
            return 0;
        }
        cout<<f(n)<<endl;
    }
    return 0;
}