分月饼 - 华为OD统一考试（C卷）- 免费看题解

题目描述

中秋节，公司分月饼，m个员工，买了n个月饼，m<=n，每个员工至少分1个月饼，但可以分多个，单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2，Max1-Max2<=3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n)，Max(n-1)-Max(n)<=3问有多少种分月饼的方法?

输入描述

每一行输入m n，表示m个员工，n个月饼，m<=n

输出描述

输出有多少种月饼分法

示例1

输入：
2 4

输出：
2

说明：
分法有2种
4=1+3
4=2+2
注意:1+3和3+1算一种分法

示例2

输入：
3 5

输出：
2

说明：
5=1+1+3
5=1+2+2

示例3

输入：
3 12

输出：
6

说明：
满足要求的有6种分法:
12=1+1+10(Max1=10,Max2=1，不满足要求)
12=1+2+9(Max1=9,Max2=2,不满足要求)
12=1+3+8(Max1=8,Max2=3 不满足要求)
12=1+4+7(Max1=7,Max2=4,Max3=1, 满足要求)
12=1+5+6(Max1=6,Max2=5,Max3=1，不满足要求)
12=2+2+8(Max1=8,Max2=2,不满足要求)
12=2+3+7(Max1=7,Max2=3,不满足要求)
12=2+4+6(Max1=6,Max2=4,Max3=2，满足要求)
12=2+5+5(Max1=5,Max2=2，满足要求)
12=3+3+6(Max1=6,Max2=3,满足要求)
12=3+4+5(Max1=5,Max2=4,Max3=3，满足要求)
12=4+4+4(Max1=4,满足要求)

题解

一、递归+回溯：
首先，每个员工至少分到一个月饼，因此可以将每个员工分到一个月饼后，剩余的月饼数量为n - m。然后，可以枚举分配多余月饼的情况，并递归计算方案数。
因题目（1,2,3）（1,3,2）（2,1,3）（2,3,1）是一同一种分配月饼的方法，因此需要去除重复的方案，我们只考虑递减的分配方案（即第 i + 1个人分配的月饼数 <= 第 i 个人分配的月饼数）。
二、动态规划：
从每个员工分到一个月饼后，剩余的月饼数量K = n - m 如何分配？
我们创建一个数组 int[][][] dp = new int[K+1][m+1][K+1]; dp[i][j][k] 表示剩余i个月饼分给m个员工并且第i个员工分到k个月饼。
状态转移方程：dp[i][j][k] = dp[i - k][j - 1][k] + dp[i - k][j - 1][k+1] + dp[i - k][j - 1][k+2] + dp[i - k][j - 1][k+3];
初始化：dp[i][1][i] = 1;// 只有一个人时，月饼全部分给这个人

Java

递归+回溯：

public static int divide(int n, int m) {
	int[] arr = new int[m];
	for (int i = 0; i < m; i++) {
		arr[i] = 1;
	}
	if (n == m){
		return 1;
	}
	return backtrack(m, n-m, 0, arr);
}

private static int backtrack(int m, int k, int index, int[] arr) {
	// 每个人都分配好了月饼时，看月饼是否分配完
	if (index == m) {
		if (k == 0){
			return 1;
		} else if (k > 0) {
			return 0;
		}else {
			return 0;// k没有小于0的情况
		}
	}
	// 月饼提前分配完，看是否满足差额限制
	if (k == 0){
		if (arr[index] >= arr[index - 1]-3){
			return 1;
		}else {
			return 0;
		}
	}
	int result =0;
	// 还剩k个月饼要分配，已经分到index位置
	for (int i = 1; i <= k; i++) {
		int value = arr[index] + i;
		// 当前位置，分配i个月饼满足条件则继续下个位置，否则直接返回0
		if (index==0 || (index>0 && arr[index - 1] >= value && value >= arr[index - 1]-3)){
			arr[index] += i;
			// 递归
			result += backtrack(m, k-i, index+1, arr);
			// 回溯
			arr[index] -= i;
		}
	}
	return result;
}

动态规划：

public static int divide2(int n, int m) {
	int K = n-m;
	int[][][] dp = new int[K+1][m+1][K+1];
	for (int i = 0; i < K+1; i++) {
		// 只有一个人时，月饼全部分给这个人是一种方案
		dp[i][1][i] = 1;
	}
	for (int i = 1; i <= K; i++) {
		for (int j = 2; j <= m; j++) {
			// 枚举最后一个员工分到的月饼数量
			for (int k = 0; k <= i; k++) {
				// 因为相同分配方案只是顺序不一样，也认为是同一个，所以我们假设分配结果中，员工获得月饼数是递减的
				// 如果第j位员工获取k个月饼，那么第j-1个员工的月饼数只能是k,k+1,k+2,k+3这四种情况
				dp[i][j][k] = dp[i - k][j - 1][k];
				if (k+1<K+1){
					dp[i][j][k] += dp[i - k][j - 1][k+1];
				}
				if (k+2<K+1){
					dp[i][j][k] += dp[i - k][j - 1][k+2];
				}
				if (k+3<K+1){
					dp[i][j][k] += dp[i - k][j - 1][k+3];
				}
			}
		}
	}
	return Arrays.stream(dp[K][m]).sum();
}