问题描述
每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。
每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法)
每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法)
输入格式
两个整数,表示m和n
输出格式
一个整数,表示队伍的排法的方案数。
样例输入
3 2
样例输出
5
数据规模和约定
m,n∈[0,18]
问题分析
问题分析
m个人还鞋,n个人借鞋。
设式子为f(m,n),如果有人还鞋,那接下来就有两种情况,有人还鞋或者有人借鞋。式子就变为f(m-1,n)+f(m,n-1)。
如果m<n,f(m,n)=0.如果n=0,那么f(m,n)=1.
package lanqiao.improve; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BAshoes { public static int ba(int m,int n){ int[][] result = new int[m+1][n+1];//解决了困扰我许久的问题。定义数组都是定义m+1。是为了递推方程的判断的时候不会出现数组越界。 for(int i =1;i<=m;i++){ result[i][0] = 1; for(int j =1;j<=n;j++){ if(i >= j){ result[i][j] = result[i-1][j] + result[i][j-1]; } } } return result[m][n]; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] strs = br.readLine().split(" "); int m = Integer.parseInt(strs[0]); int n = Integer.parseInt(strs[1]); System.out.println(ba(m,n)); } }