题目描述

一个楼梯共有 n级台阶，每次可以走一级或者两级或者三级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。

(递归) $O(n^2)$

这里递归思想只需要自己多算一下其他阶的规律就可以得到了,其实就是一个斐波那契数列.

C++ 代码

#include <iostream>

using namespace std;

int a[20] = {1, 1, 2};

int main()
{
    int n;
    cin >> n;
    for (int i = 3; i <= n; i ++)
    a[i] = a[i - 1] + a[i - 2] + a[i - 3];
    cout << a[n];

    return 0;
}

(DFS) $O(n^2)$

非常傻的每种情况都试,如果符合情况就增加答案,如果不符合就跳出当前函数

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n,ans;

void dfs(int u){
    if(u == n){
        ans++;
        return;
    }//符合情况
    if(u>n) {
        return;
    }//不符合情况
    dfs(u + 1);//如果只走一级台阶
    dfs(u + 2);//如果只走两级台阶
    dfs(u + 3);//如果只走三级台阶
}

int main(){
    cin>>n;
    dfs(0);
    cout<<ans;
    return 0;
}