算法训练 未名湖边的烦恼 dp

　　问题分析

思路:

dp[i][j]为所可能的排列总数  i 表示 i个还鞋的人数   j 表示 j个租鞋的人数

状态转移方程：

dp[i][0]=1;

dp[i][j]=dp[i-1][j]+dp[i][j-1]；（i>=j）

其余为0；

我们知道:假设还鞋为m 租鞋为n

选择时我们第一个必须为m,第二个我们可以选择m也可以选择n,第三个如果我们第二个选择的为n则此时必须选择m,如果我们第二步选择了m的话,那上下的又回到了第二步的选择,依次往下进行第四步第五步。。。

可的到如下关系: 把第dp[i-1][j]，这时表示i-1个人还和j个人租时的所有排列情况，在所有排列情况下最后再排一个还鞋的人，就可以满足i个人还鞋j个人租鞋的情况。

同理，在dp[i][j-1]时表示i个人还和j-1个人租时的所有排列情况，后面再排一个租鞋的人，得到dp[i][j]=dp[i-1][j]+dp[i][j-1]，即i,j的所有排序情况、

#include<bits/stdc++.h>using namespace std;int dp[20][20];int main(){	int n,m,i,j;	scanf("%d %d",&m,&n);	dp[1][0]=1;	for(i=1;i<=18;i++)		for(j=1;j<=18;j++)		{			dp[i][j]=dp[i-1][j]+dp[i][j-1];		}		PRintf("%d/n",dp[m][n]);		return 0; }