$\it{***方法一(简单递归)***}$
思路:
利用回溯和递归
思想,简单化问题,一步步拆解直至最小可解
问题
要点:
到第n级台阶只可能是从第n-2级直接走两级或者从第n-1级走一级
即:到第n级台阶(0$\rightarrow$n)的方案数可以拆解为到n-2级台阶(0$\rightarrow$n-2)的方案数加上到n-1级台阶(0$\rightarrow$n-1)的方案数
#include<bits/stdc++.h>
using namespace std;
int foo(int n)
{
if(n==1) return 1;
else if(n==2) return 2;
return foo(n-2)+foo(n-1);
}
int main()
{
int n;
cin>>n;
cout<<foo(n);
return 0;
}
$\it{***方法二(简单DFS)***}$
图解:
#include<bits/stdc++.h>
using namespace std;
int n;
int ans;
void f(int k)
{
if(k==n) ans++;
else if(k<n)
{
f(k+1);
f(k+2);
}
}
int main()
{
cin>>n;
f(0);
cout<<ans<<endl;
return 0;
}