算法训练 未名湖边的烦恼
算法训练 未名湖边的烦恼
时间限制：1.0s 内存限制：256.0MB
问题描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。 每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）
输入格式
两个整数，表示m和n
输出格式
一个整数，表示队伍的排法的方案数。
样例输入
3 2
样例输出
5
数据规模和约定
m,n∈［0,18］ 问题分析
分析：假设3个人还，2个人借，假设还为A，借为B，能够满足条件的答案为
AABB A
ABAB A
AAAB B
AABA B
ABAA B
找到的规律是，它的上一步是要么2还2借，下一次为还，要么3还1借，下一次是借
f(int m, int n)
{
.......
return f(m - 1, n) + f(m, n - 1); // 分别为下一次为还，下一次为借
}如果依次递归到借的n == 0，那么不借肯定成立，这是一种情况，题目说明两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法，那么3个A，还的顺序不同也算一种情况。
至于f(m - 1, n) + f(m, n - 1)的前一种情况f(m-1, n)，可能出现之后m < n，那么不成立，return 0，接着到f(m, n-1)情况去，会递归到n == 0情况，这样所有可能的情况都包含了
有人会想m == n情况，或者m>=n情况，这些不用判断，m==n，可能BAAB,BBAA,BABA,ABBA这些都不成立的，只需要跟着最初列出的递归式子想就行了，最后加上动态规划，速度就有所提升。
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static int[][] dp = new int[19][19];
public static int f(int m, int n) {
if (dp[m][n] != -1)
return dp[m][n];
if (m < n)
return dp[m][n] = 0;
if (n == 0)
return dp[m][n] = 1;
return dp[m][n] = f(m, n - 1) + f(m - 1, n);// 分别为此次借，此次还，情况相加即为所求
}
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int m = cin.nextInt();
int n = cin.nextInt();
cin.close();
for (int i = 0; i < 19; ++i) {
for (int j = 0; j < 19; ++j) {
dp[i][j] = -1;
}
}
System.out.println(f(m, n));
}
}
腾讯云开发者
