题目描述与示例
题目描述
中秋节，公司分月饼，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
输出描述
输出有多少种月饼分法
示例
输入
2 4
输出
2
说明
分法有2种:
4=1+3
4=2+2
注意: 1+3和3+1算一种分法
解题思路
用比较严谨的数学语言表达上述问题为：挑选出m非递减的数，要求相邻两个数的差值不超过3，这m个数的和为n，问一共有多少种挑选方式。
由于在挑选完第i个数之后，第i+1个数的取值和第i个数的取值相关，很容易想到用动态规划来解决上述问题。思考动态规划三部曲：
dp数组的含义是什么？
我们需要考虑三个因素，选择了第几个数，这个数取了什么数值，当前总和为多少。因此需要构建一个三维的dp数组。
考虑dp[i][j][k]表示，第i个数取值为j时，前i个数的总和为k的方法数。
分别考虑i，j，k三个数的取值范围来确定dp数组的大小。
i和k的定义比较明确，范围分别是[1, m]和[1, n]。
每个数字的取值j的最小为1，最大的情况为m-1个数字都选择最小数1，剩余一个最大数选择n-(m-1) = n-m+1。故j的取值范围是[1, n+m+1]
故构建dp数组是一个大小为(m+1)*(n-m+2)*(n+1)的三维数组。
- 动态转移方程是什么？
假设第i个数的取值为j，那么第i+1个数只能在j，j+1，j+2，j+3中进行挑选。
若此时前i个数的总和为k，那么当第i+1个数
- 取了
j时，前i+1个数的总和为k+j。存在dp[i+1][j][k+j] += dp[i][j][k] - 取了
j+1时，前i+1个数的总和为k+j+1。存在dp[i+1][j+1][k+j+1] += dp[i][j][k] - 取了
j+2时，前i+1个数的总和为k+j+2。存在dp[i+1][j+2][k+j+2] += dp[i][j][k] - 取了
j+3时，前i+1个数的总和为k+j+3。存在dp[i+1][j+3][k+j+3] += dp[i][j][k]
上述四个式子可以合并为一个式子，即dp[i+1][j+d][k+j+d] += dp[i][j][k]，其中d的取值为[0,3]
先从小到大遍历i，再从小到大遍历j，再从小到大遍历k，则代码如下
python">for i in range(1, m):
for j in range(1, n-m+2):
for k in range(i, n+1):
for d in range(4):
if j+d < n-m+2 and k+j+d < n+1:
dp[i+1][j+d][k+j+d] += dp[i][j][k]
dp数组如何初始化？
i = 0没有实际意义，不考虑。
考虑i = 1的情况，第1个数字的取值j最小为1，最大为n // m（即所有数字尽可能接近的情况），即此时j的取值为[1, n // m]。
同时，由于只选择了一个数字，因此此时前i个数字的总和k = j
故对于i = 1，做如下初始化
python">dp = [[[0] * (n+1) for j in range(n-m+2)] for i in range(m+1)]
for j in range(1, n//m+1):
dp[1][j][j] = 1
dp[1][j][j] = 1表示只对应1种方法数。
代码
Python
python"># 题目：【DP】2023C-分月饼
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：DP
# 代码看不懂的地方，请直接在群上提问
# 输入员工人数m，月饼总数n
m, n = map(int, input().split())
# dp数组是一个大小为(m+1)*(n-m+2)*(n+1)的三维数组
# dp[i][j][k]表示，第i个数取值为j时，前i个数的总和为k的方法数
dp = [[[0] * (n+1) for j in range(n-m+2)] for i in range(m+1)]
# 第1个数字选了j，此时总和为j
# j的取值范围是[1, n//m]
# 因为m个数的和需要为n，那么最小那个数的最大值是n//m
for j in range(1, n//m+1):
dp[1][j][j] = 1
# i的最大取值为m-1
for i in range(1, m):
# j的最小取值为1，最大取值为n-m+1
for j in range(1, n-m+2):
# k的最小取值为i（前i个数都选了1，和为i），最大取值为n
for k in range(i, n+1):
# 增量d的取值范围为0，1，2，3
for d in range(4):
# 条件为j+d和k+j+d都没有超过对应的最大范围
if j+d < n-m+2 and k+j+d < n+1:
dp[i+1][j+d][k+j+d] += dp[i][j][k]
ans = 0
# dp[m][j][n]表示第m个数（最后一个数）选了j后，总和为n的方法数
# 将所有的dp[m][j][n]加在一起即为答案
for j in range(n-m+2):
ans += dp[m][j][n]
print(ans)
Java
java">import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
// dp array initialization
int[][][] dp = new int[m + 1][n - m + 2][n + 1];
for (int j = 1; j <= n / m; j++) {
dp[1][j][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j <= n - m + 1; j++) {
for (int k = i; k <= n; k++) {
for (int d = 0; d < 4; d++) {
if (j + d < n - m + 2 && k + j + d <= n) {
dp[i + 1][j + d][k + j + d] += dp[i][j][k];
}
}
}
}
}
int ans = 0;
for (int j = 1; j <= n - m + 1; j++) {
ans += dp[m][j][n];
}
System.out.println(ans);
}
}
C++
#include <iostream>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
// dp array initialization
int dp[m + 1][n - m + 2][n + 1] = {0};
for (int j = 1; j <= n / m; j++) {
dp[1][j][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j <= n - m + 1; j++) {
for (int k = i; k <= n; k++) {
for (int d = 0; d < 4; d++) {
if (j + d < n - m + 2 && k + j + d <= n) {
dp[i + 1][j + d][k + j + d] += dp[i][j][k];
}
}
}
}
}
int ans = 0;
for (int j = 1; j <= n - m + 1; j++) {
ans += dp[m][j][n];
}
cout << ans << endl;
return 0;
}
时空复杂度
时间复杂度：O(NM(N-M))。三重循环所需时间复杂度。
空间复杂度：O(NM(N-M))。三维dp数组所需空间。
