問題分析

思路:

dp[i][j]為所可能的排列總數(shù)  i 表示 i個還鞋的人數(shù)   j 表示 j個租鞋的人數(shù)

狀態(tài)轉(zhuǎn)移方程：

dp[i][0]=1;

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

其余為0；

我們知道:假設(shè)還鞋為m 租鞋為n

選擇時我們第一個必須為m,第二個我們可以選擇m也可以選擇n,第三個如果我們第二個選擇的為n則此時必須選擇m,如果我們第二步選擇了m的話,那上下的又回到了第二步的選擇,依次往下進行第四步第五步。。。

可的到如下關(guān)系: 把第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; }