华为一面，差点栽了。。

大家好，我是吴师兄。

昨天有个同学报喜， 主管面结束了，等 offer 审批就行 ，看了一下报名日期，嚯，真 20 天拿下 offer！

不过有点可惜的是，机试后的一面手撕环节没有表现好导致级别没有到 d3，可惜可惜，今天来看看这道手撕题。

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

举个例子：

输入：2 4
输出：2
解释：分法有2种
4=1+3
4=2+2
注意: 1+3和3+1算一种分法

用比较严谨的数学语言表达上述问题为：挑选出 m 个非递减的数，要求相邻两个数的差值不超过 3 ，这 m 个数的和为 n ，问一共有多少种挑选方式。

由于在挑选完第 i 个数之后，第 i+1 个数的取值和第 i 个数的取值相关，很容易想到用动态规划来解决上述问题。

老规矩，思考动态规划三部曲：

1、 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) 的三维数组。

2、动态转移方程是什么？

假设第 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 ，则代码如下

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 2 and k+j+d 1:
                    dp[i+1][j+d][k+j+d] += dp[i][j][k]

3、 dp 数组如何初始化？

i = 0 没有实际意义，不考虑。

考虑 i = 1 的情况，第 1 个数字的取值 j 最小为 1 ，最大为 n // m （即所有数字尽可能接近的情况），即此时 j 的取值为 [1, n // m] 。

同时，由于只选择了一个数字，因此此时前 i 个数字的总和 k = j

故对于 i = 1 ，做如下初始化

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 种方法数。

代码如下：

# 输入员工人数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 2 and k+j+d 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)

再来优化一小波，加分项：

1. 减少内存使用 ：

• 由于 dp 数组的第三维 k 依赖于前一维的值，可以考虑使用滚动数组技术，仅保留两层 dp 数组，减少空间复杂度。

• 在循环中加入边界检查，避免数组越界错误，如 if j+d < len(dp[0]) and k+j+d < len(dp[0][0]): 。

• 考虑到 j 的最大值，可以将 n//m+1 改为 min(n-m+1, n//m+1) 以减少不必要的计算。

下面是优化后的代码框架：

m, n = map(int, input().split())
dp = [[0] * (n+1) for _ in range(n-m+2)]

# 初始化
for j in range(1, min(n-m+1, n//m+1)):
    dp[j][j] = 1

for i in range(1, m):
    new_dp = [[0] * (n+1) for _ in range(n-m+2)]
    for j in range(1, n-m+2):
        for k in range(i, n+1):
            for d in range(4):
                if j+d and k+j+d 0]):
                    new_dp[j+d][k+j+d] += dp[j][k]
    dp = new_dp

ans = sum(dp[j][n] for j in range(len(dp)))
print(ans)

在原始的代码中，我们使用了一个完整的三维 dp 数组，其维度为 (m+1) x (n-m+2) x (n+1) 。但在优化后的代码中，我们实际上是在每一层迭代中只保留了当前层和前一层的数据，而不是整个三维数组。

这里的关键在于“滚动数组”技术的应用。在优化后的代码中，我们每次迭代只关注 i 和 i+1 这两层的状态，而不需要保存所有 i 层的信息。具体来说：