写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：P2089 烤鸡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述：
输入格式：
一个正整数 n，表示美味程度。
输出格式：
第一行，方案总数。
第二行至结束，10 个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个 0。
输入样例： 11 输出样例： 10 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1
/
提示：
对于 100% 的数据，n ≤ 5000。
解题思路：
我们使用深度优先搜索的时候，
第一个要注意的点是搜索的顺序，
因为我们要保证，
我们写出的递归结构能够遍历所有情况，
在我们初学搜索的时候，我们一定要画一个递归搜索树观察，
递归非常抽象，画图能很好的帮助我们解题。（以上递归搜索的基本思路，多熟悉总是好的）
接下来是具体思路：
我们之前练习了三道模板题，dfs的题目的思路大多是他们的变式：
1. 指数级枚举
2. 排列型枚举
3. 组合型枚举
我们可以从这三个角度思考这道题目，
我们一共使用10种调料，
而每种调料有三种选择，1、2、3克，这其实与指数级枚举类似，
让我们来画一下递归搜索树：
根节点：（我们就那一种情况举例画图）
它有三种选择可以往下递归搜索：
然后第二个数也有三种选择：
第三个数也有三种选择：
以此类推，就能搜索出所有的情况了。
下面是代码实现：
代码：
//包常用头文件 #include #include #include #include #include using namespace std; //根据题目开大小 const int N = 20; int n; //需要返回的情况数量 int ret = 0; //记录数据 int arr[N]; //用二维数组存需要输出的值 vector> res; void dfs(int u, int sum) { //如果总和已经比n大，直接返回（剪枝） if(sum > n) return; if(u > 10) { //如果符合要求就存进数组 if(sum == n) { vector v; ret++; for(int i = 1; i <= 10; i++) { v.push_back(arr[i]); } res.push_back(v); } return; } //搜索 for(int i = 1; i <= 3; i++) { arr[u] = i;//记录数据 dfs(u + 1, sum + i); arr[u] = 0;//恢复现场 } } int main() { scanf("%d", &n); dfs(1, 0); printf("%d\n", ret); //输出 for(int i = 0; i < ret; i++) { for(int j = 0; j < 10; j++) { printf("%d ", res[i][j]); } puts(""); } return 0; }
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
