问题描述
  每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。
  每天早上,租鞋窗口都会排起长龙,假设有还鞋的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));
    }
}

  

01-22 03:03