提供一种dfs解法

看到是方案数，想到是dp或dfs，看到标题想到dfs

---

先设状态，很容易想到是当前在第几阶台阶

考虑搜索，题目中只给了两条分支，一条是走1步，一条是走3步，所以

void dfs(int sum){
    dfs(sum+1);
	dfs(sum+3);
}

OK这样就写好了分支

---

考虑边界（其实应该首先考虑边界）

在猴子到达山洞的时候就停下来不要走了（即所谓的有解），记录答案，返回

void dfs(int sum){
	if(sum==n){
		ans++;
		return ;
	}
	dfs(sum+1);
	dfs(sum+3);
}

OK这样边界也写完了

OK但是如果测试一下就会爆栈，因为当sum>n的时候，无论再怎么加也没办法到达边界，所以还要特判一下

void dfs(int sum){
	if(sum==n){
		ans++;
		return ;
	}
	if(sum>n){
		return ;
	}
	dfs(sum+1);
	dfs(sum+3);
}

---

OK这样递归函数就写好了

考虑起点，小猴子从第0级开始走，根据参数定义，很容易想到dfs(0)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//const int N=;
int n,ans;

void dfs(int sum){
	if(sum==n){ //到达山顶 
		ans++;
		return ;
	}
	if(sum>n){ //永远也到不了 
		return ;
	}
	dfs(sum+1); //走一步分支 
	dfs(sum+3); //走两步分支 
}

int main(){
	//输入输出优化 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	dfs(0); //从0级开始走 
	cout<<ans;
	return 0;
}

OK呀时间来到了惊人的400ms，其实这样效率是相当低的，可以通过dp来优化一下

具体dp做法参考其他题解

---

小结：

1.涉及的算法：dfs(深度优先搜索)

2.时间复杂度：指数级复杂度(非常高，数据稍微大一点就爆了)

3.难度：入门，J的第一题都当不上