本文最后更新于 874 天前,其中的信息可能已经有所发展或是发生改变。
821. 跳台阶 (递归搜索树 · 一维)
原题链接
描述
一个楼梯共有 n 级台阶,每次可以走一级或者两级,问从第 0 级台阶走到第 n 级台阶一共有多少种方案。
输入格式
共一行,包含一个整数 n。
输出格式
共一行,包含一个整数,表示方案数。
数据范围
1≤n≤15
输入样例:
5
输出样例:
8
分析
- 每次跳台阶都有两种方式选择,即每个台阶都是一个树的结点
- 满足条件则计数加一
代码
#include <bits/stdc++.h>
using namespace std;
int ans=0,n; //定义ans存储答案,n为满足答案的条件
void ff(int k){ //递归遍历
if(k==n){ //满足答案ans++
ans++;
}
else if(k<n){ //未到达条件时进行选择
ff(k+1);
ff(k+2);
}
}
int main(){
cin>>n;
ff(0); //从0开始递归
cout<<ans;
return 0;
}