——以“未名湖畔的烦恼”为例
题目描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）
输入格式
两个整数，表示m和n
输出格式
一个整数，表示队伍的排法的方案数。
数据规模和约定
m,n∈［0,18]
题目分析
看到题目的第一反应，北大那么有钱为什么还会差冰鞋（doge）。
先看题干，对于排队方案的总数计算，交换相同需求的人算同一种拍法，数据规模也不大，也就是说整个搜索树不会超过36层。
那就想到使用深度优先搜索来解决问题。也就是我们今天要讨论的问题——什么是“深度优先搜索”。
所谓深度优先搜索，本质还是搜索，深度优先只是一种搜索策略。搜索的本质是对所有的可能情况进行遍历与验证的过程，不过这也有别于数学意义上的穷举法。当我们在将搜索树沿深度方向向下延伸的过程当中，我们其实也在不断地进行剪枝的操作，并以此可以大幅加快搜索步骤。
说了这么多，还是先上图。
如此进行反复的判断与剪枝操作，也就是通过
return true 进入下一层
return false 剪枝或结束
来实现
最后，上代码！
代码
/*
* @Author: Gehrychiang
* @Date: 2019-11-05 13:40:11
* @Last Modified by: Gehrychiang
* @Last Modified time: 2019-11-07 13:43:08
* @Email:gehrychiang@ailiyun.com
* @Website:www.yilantingfeng.site
*/
#include <iostream>
#include <cstdio>
using namespace std;
int sum=0;
bool dfs(int rm, int rn,int pool)
{
if (rm==0&&rn==0)
{
++sum;
return false;
}
if (rm>=1&&dfs(rm-1,rn,pool+1))
{
return true;
}
if (pool-1>=0&&rn>=1&&dfs(rm,rn-1,pool-1))
{
return true;
}
return false;
}
int main(int argc, char const *argv[])
{
int m,n;
cin>>m>>n;
dfs(m,n,0);
cout<<sum;
return 0;
}