算法训练 未名湖边的烦恼

思路：

没有感觉特别大的障碍，读题费了点功夫。要注意一句话：（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）

可以理解为只有m人还鞋，没有人租鞋的时候，无论这m个人怎么排列都只看作一种方案

递推方程很好写：dp[i][j]=dp[i-1][j]+dp[i][j-1]，还鞋或者租鞋的人减少一个状态相加得来

代码：

#include<iostream>#include<string>#include<cstring>using namespace std;const int MAXN=19;int dp[MAXN][MAXN];void init(){    memset(dp,0,sizeof(dp));    for(int i=0;i<MAXN;i++)        dp[i][0]=1;//（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）所以不用求阶乘了+_+，想的有点多    for(int i=1;i<MAXN;i++)    {        for(int j=1;j<MAXN;j++)        {            if(i>=j)                dp[i][j]=dp[i-1][j]+dp[i][j-1];        }    }}int main(){    init();    int m,n;    scanf("%d%d",&m,&n);    PRintf("%d/n",dp[m][n]);    return 0;}