1、未名湖畔的烦恼

题目描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙。假设有还鞋的人m个，有需要租鞋的人n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）

---

输入格式　
两个整数m、n

---

输出格式　　
一个整数——队伍排法的方案数

---

样例
输入3 2，输出5

---

数据规模和约定　　
m,n∈［0,18］

分析题目：因为前一天鞋都被借走了（第二天来还或者随便任何某个想还的时间）…好吧，我分析不出来什么（因为我觉得这并不符合实际情况，实际情况是有人来借就给，没有鞋能给的话就等着来还鞋的，所以为什么要设计那么多种方案呢），我们还是就按照题目的表面意思写程序吧！
程序：想写程序，又没有思路…

#include <iostream>
#include <stdlib.h>
using namespace std;
int fun(int m, int n)
{if (m < n)return 0;if (n == 0)return 1;return fun(m - 1, n) + fun(m, n - 1);
}
int main()
{int returnNum, rentNum;cout << "还鞋人数returnNum(0~18)：";cin >> returnNum;cout << "租鞋人数rentNum(0~18)：";cin >> rentNum;cout << "方案数：" << fun(returnNum, rentNum) << endl;system("pause");return 0;
}

【碎碎念】
刚开始刷算法题，这是第一道遇见的有难度的题，靠我自己的水平是想不到答案的。我花费了一个半小时在找每个输出之间的规律，比如当m = 5, n = 1,2,3,4,5时各个方案数的联系，事实是这是徒劳的，没有规律可循。即便写出了几个符合的算法，也还是有例外。很明显，我这种思想体现了我的算法水平是如何的低…于是乎我搜索了答案。在看了多个别人的理解后，我有了自己的理解，目前来说，我只是能看懂，能否做到举一反三？
【理解】
1、首先要明确的：根据一个大神的讲解，我知道了该递归算法的排列是倒着来的，也就是说，先看队伍的第五个人是换鞋还是借鞋…原因是若不这样做，我们无法做到让算法在先对第一个人进行排列时保证他是来还鞋的。而先看队伍的第五个人是换鞋还是借鞋，最后再根据判断n是否为0来确保队伍上的第一个人是还鞋的。这样，就保证了第一个人是还鞋的。
2、然后我根据实例进行了验证。有五种方式，如下：

3、开始分析意义。第⑤条路径最短最好分析！会有很惊奇的发现！从下往上分析，这是肯定的呐。

• （3,0）表示还有3个要还鞋的人还没排呢。但是不用排了呀。因为算法排出的结果为BBAAA，但实际排队效果为AAABB！所以！到这里你会发现…m - 1表示我这一步把某个还鞋的人安排了，n - 1表示我这一步把某个借鞋的人安排了！（Oh，当然，我比较愚钝，可能你早就发现了…）因此！各个路径从上到下下来的结果分别如下（实际效果与之相反）：
  ①ABAB(A)
  ②ABBA(A)
  ③BAAB(A)
  ④BABA(A)
  ⑤BBAA(A)

4、看懂整个算法后，进行总结。

• 每次走完整个流程，符合n = 0的话，就表示刚才走的路径符合要求，所以返回1，表示这是一种方式。
• 我不知道一个题要具备怎样的特征就要去想着应该用递归去做；更不知道如果需要写递归的话，这个递归应该是怎样的。
• 把m、n的减1看做对其进行了安排，也就想爬台阶那个题的减1、减2表示你实际爬台阶的行动。
• 先不总结了…做的题比较少的原因吧，总结不出来个啥。也许等做多了就会有所感悟…我会再来写的！