保姆级教程：用记忆化递归和动态规划优化‘放苹果’问题，告别OpenJudge超时

从递归到动态规划：彻底掌握‘放苹果’问题的优化艺术

第一次在OpenJudge上遇到"放苹果"问题时，我天真地以为这不过是个简单的递归练习题。直到提交后看到刺眼的"Time Limit Exceeded"，才意识到问题的复杂性远超预期。这道看似简单的题目，实则是检验算法优化能力的绝佳试金石——它完美展示了从朴素递归到记忆化递归，再到动态规划的完整优化路径。

1. 问题本质与朴素递归解法

"放苹果"问题的核心是计算将M个相同的苹果放入N个相同的盘子中的不同分法数量。这里的"相同"意味着苹果和盘子都是不可区分的，因此分法(1,2)和(2,1)被视为同一种方案。

1.1 问题建模与递归关系

让我们从最直观的递归思路开始。定义函数f(m,n)表示将m个苹果放入n个盘子的方案数，我们可以建立以下递归关系：

1. 基准情况：

   • 当m=0（没有苹果）：只有一种分法——所有盘子都为空
   • 当n=1（只有一个盘子）：所有苹果必须放在这个盘子里
   • 当m=1（一个苹果）：只能放在任意一个盘子里，由于盘子相同，只有一种分法

2. 递归情况：

   • 如果苹果比盘子少(m < n)：必然有n-m个盘子为空，等价于f(m,m)
   • 否则，考虑两种子情况：
     • 至少有一个盘子为空：方案数等于f(m,n-1)
     • 所有盘子都有苹果：先在每个盘子放一个苹果，剩下的m-n个苹果再分配到n个盘子，即f(m-n,n)

def count_ways(m, n): if m == 0 or m == 1 or n == 1: return 1 if m < n: return count_ways(m, m) return count_ways(m, n-1) + count_ways(m-n, n)

1.2 朴素递归的性能瓶颈

虽然这个递归解法逻辑正确，但它的时间复杂度是指数级的O(2^(m+n))。当m和n稍大时（比如m=n=10），函数调用次数会爆炸式增长：

f(10,10) = f(10,9) + f(0,10) = [f(10,8) + f(1,9)] + 1 = [[f(10,7) + f(2,8)] + [f(1,8) + f(-8,9)]] + 1 = ...

这种重复计算的规模会随着参数增大而急剧膨胀，这正是导致OpenJudge上TLE的根本原因。

2. 记忆化递归：消除重复计算的利器

2.1 记忆化技术原理

记忆化(Memoization)是一种优化技术，它通过存储已计算的结果来避免重复计算。对于递归函数，我们可以建立一个缓存（通常用数组或字典实现），在每次计算前先检查缓存，如果结果已存在就直接返回，否则才进行计算并将结果存入缓存。

2.2 实现记忆化递归

让我们改造前面的朴素递归，加入记忆化：

def count_ways_memo(m, n, memo=None): if memo is None: memo = {} if (m, n) in memo: return memo[(m, n)] if m == 0 or m == 1 or n == 1: result = 1 elif m < n: result = count_ways_memo(m, m, memo) else: result = count_ways_memo(m, n-1, memo) + count_ways_memo(m-n, n, memo) memo[(m, n)] = result return result

2.3 性能对比分析

让我们通过实际数据感受记忆化的威力：

记忆化将时间复杂度从指数级降低到了多项式级O(m*n)，因为每个子问题(m',n')只需计算一次。这使得算法能够处理更大的输入规模，有效避免了TLE。

3. 动态规划：自底向上的高效解法

3.1 动态规划思想

动态规划(Dynamic Programming)与记忆化递归思想相通，但采用自底向上的迭代方式。它通常更高效，因为避免了递归的函数调用开销，而且可以更精细地控制计算顺序。

3.2 DP状态定义与转移方程

对于"放苹果"问题，我们定义dp[i][j]表示i个苹果放入j个盘子的方案数。状态转移方程与递归关系相同：

dp[i][j] = 1, 当i=0或i=1或j=1 = dp[i][i], 当i<j = dp[i][j-1] + dp[i-j][j], 当i>=j

3.3 DP表格实现

我们可以用二维表格来实现这个DP解法：

def count_ways_dp(m, n): dp = [[0]*(n+1) for _ in range(m+1)] for i in range(m+1): for j in range(1, n+1): if i == 0 or i == 1 or j == 1: dp[i][j] = 1 elif i < j: dp[i][j] = dp[i][i] else: dp[i][j] = dp[i][j-1] + dp[i-j][j] return dp[m][n]

3.4 DP优化技巧

对于竞赛场景，我们还可以进一步优化：

1. 空间优化：当前解法空间复杂度为O(m*n)，可以优化到O(n)：

   def count_ways_dp_optimized(m, n): dp = [1] * (n+1) # 对应i=0或i=1的情况 for i in range(2, m+1): new_dp = [1] # j=0的情况 for j in range(1, n+1): if i < j: new_dp.append(new_dp[i]) else: new_dp.append(new_dp[j-1] + dp[j]) dp = new_dp return dp[n]

2. 预处理：对于多组查询，可以预先计算所有可能的m和n，然后O(1)回答每个查询：

   max_m = 10 max_n = 10 dp = [[0]*(max_n+1) for _ in range(max_m+1)] # 预处理填充dp表格 for i in range(max_m+1): for j in range(1, max_n+1): if i == 0 or i == 1 or j == 1: dp[i][j] = 1 elif i < j: dp[i][j] = dp[i][i] else: dp[i][j] = dp[i][j-1] + dp[i-j][j] # 查询函数 def query(m, n): return dp[m][n]

4. 竞赛实战技巧与常见陷阱

4.1 输入规模与算法选择

在信息学竞赛中，选择合适算法的关键在于分析输入规模：

4.2 常见错误与调试技巧

1. 数组越界：确保DP表格大小足够，特别是当m=n时：

   # 错误：当i=j时，i-j=0可能越界 dp[i][j] = dp[i][j-1] + dp[i-j][j] # 正确：已经处理了i<j的情况

2. 初始化错误：特别注意边界条件的初始化：

   # 必须初始化j=1的情况 for i in range(m+1): dp[i][1] = 1

3. 整数溢出：虽然Python不用担心，但在C++/Java中要注意：

   // 使用long long而不是int long long dp[MAX_M][MAX_N];

4.3 性能测试与对比

让我们用实际数据对比三种方法的性能（单位：毫秒）：

提示：在竞赛中，即使记忆化递归和DP理论复杂度相同，DP通常更快，因为它避免了递归开销和哈希表查询。

4.4 洛谷P2386的特殊考量

洛谷上的放苹果问题(P2386)通常有严格的时间限制，建议：

1. 使用动态规划而非记忆化递归
2. 采用快速输入输出方法（特别是C++）
3. 考虑空间优化版的DP
4. 对于极端情况（如m=200,n=200），可能需要进一步优化

// 洛谷P2386的推荐解法（C++） #include <iostream> #include <vector> using namespace std; int main() { int t, m, n; cin >> t; while (t--) { cin >> m >> n; vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); for (int i = 0; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (i == 0 || i == 1 || j == 1) { dp[i][j] = 1; } else if (i < j) { dp[i][j] = dp[i][i]; } else { dp[i][j] = dp[i][j-1] + dp[i-j][j]; } } } cout << dp[m][n] << endl; } return 0; }

5. 数学视角与进阶优化

5.1 问题等价与组合数学

"放苹果"问题实际上等价于：

• 将整数m划分为最多n个部分的划分数
• 将m个不可区分的物品分成n个不可区分的组

这在组合数学中被称为"划分数"问题，有专门的生成函数和研究方法。

5.2 五边形数定理优化

对于非常大的m和n（比如m,n>1000），可以使用基于五边形数定理的O(m√m)算法：

def partition_number(m, n): partitions = [0]*(m+1) partitions[0] = 1 for k in range(1, m+1): i = 0 pentagonal = 1 while pentagonal <= k: sign = -1 if (i % 4 >= 2) else 1 partitions[k] += sign * partitions[k - pentagonal] i += 1 j = (i // 2 + 1) if (i % 2 == 0) else -(i // 2 + 1) pentagonal = j * (3*j - 1) // 2 return partitions[m] if n >= m else partitions[m] - partitions[m-n-1]

5.3 并行计算可能性

对于极端大规模问题，可以考虑并行计算：

1. 将DP表格按对角线划分
2. 每个处理器负责计算特定范围内的i,j
3. 需要仔细设计通信和同步机制

6. 变种问题与扩展思考

6.1 盘子不空的情况

如果要求每个盘子至少有一个苹果，只需修改初始条件：

• 当m < n时，方案数为0（无法满足每个盘子都有）
• 递推关系变为：f(m,n) = f(m-1,n-1) + f(m-n,n)

6.2 苹果和盘子可区分

当苹果或盘子可区分时，问题转化为完全不同的组合问题：

• 苹果不同，盘子相同：斯特林数
• 苹果相同，盘子不同：组合数
• 都不同：n^m种方法

6.3 其他相关OJ题目

1. 整数划分问题：

   • 洛谷P1025 数的划分
   • OpenJudge 2.3 666:放苹果（本质相同）

2. 变形问题：

   • 考虑盘子容量限制
   • 考虑对称性限制
   • 带有约束条件的分配

# 带盘子容量限制的变种 def count_ways_with_limit(m, n, limit): if m == 0: return 1 if n == 0: return 0 total = 0 for k in range(min(limit, m) + 1): total += count_ways_with_limit(m - k, n - 1, k) return total

在实际竞赛中，我经常遇到选手因为忽略初始条件或错误处理递归边界而失分。一个实用的调试技巧是先用小数据测试所有边界情况，比如m=0、n=0、m=1、n=1等，确保这些特殊情况都能正确处理。另外，在实现DP时，养成先写状态转移方程再写代码的习惯，可以大幅减少错误概率。