一个‘放苹果’问题，我搞懂了动态规划的入门钥匙 | C++实战
从放苹果问题解锁动态规划的核心思维
记得第一次接触动态规划时，我被那些晦涩的状态转移方程搞得晕头转向。直到遇到这个看似简单的"放苹果"问题，一切才豁然开朗。把M个苹果放进N个盘子有多少种分法？这个幼儿园级别的题目，竟然藏着理解DP的黄金钥匙。
1. 问题本质与暴力递归解法
放苹果问题要求计算将M个无差别苹果放入N个无差别盘子的分法数，顺序不同的分法视为相同（如5,1,1和1,5,1算一种）。这实际上是在求正整数M的至多N个部分的划分。
1.1 递归思维分解
最直观的方法是暴力递归——将问题分解为更小的子问题：
基本情况：
- 没有苹果（M=0）：只有一种分法——所有盘子为空
- 只有一个盘子（N=1）：只有一种分法——全部苹果放入该盘子
递归情况：
- 当盘子比苹果多（N>M）：至少有N-M个空盘子，去掉它们不影响结果
- 一般情况：分法数=至少一个盘子空着的情况+所有盘子都有苹果的情况
int countWays(int m, int n) { if (m == 0 || n == 1) return 1; if (n > m) return countWays(m, m); return countWays(m, n-1) + countWays(m-n, n); }1.2 递归树分析
以M=4，N=3为例，递归调用过程如下：
countWays(4,3) ├── countWays(4,2) // 至少一个盘子空着 │ ├── countWays(4,1) = 1 │ └── countWays(2,2) // 所有盘子都有苹果 │ ├── countWays(2,1) = 1 │ └── countWays(0,2) = 1 └── countWays(1,3) // 所有盘子都有苹果 └── countWays(1,1) = 1提示：观察递归树会发现大量重复计算，如countWays(2,2)被多次计算，这正是动态规划要优化的关键。
2. 从递归到记忆化搜索
2.1 重叠子问题识别
上述递归解法的时间复杂度是指数级的O(2^min(M,N))。通过打印递归调用，可以发现：
计算countWays(3,2) 计算countWays(3,1) 计算countWays(1,2) 计算countWays(1,1) 计算countWays(1,2) // 重复计算！2.2 记忆化实现
添加一个二维数组存储已计算结果：
int memo[11][11]; // 根据题目M,N≤10 int countWaysMemo(int m, int n) { if (memo[m][n] != 0) return memo[m][n]; if (m == 0 || n == 1) return 1; if (n > m) { memo[m][n] = countWaysMemo(m, m); } else { memo[m][n] = countWaysMemo(m, n-1) + countWaysMemo(m-n, n); } return memo[m][n]; }记忆化将时间复杂度降为O(M*N)，因为每个子问题只计算一次。
3. 动态规划表格法
3.1 DP表构建
我们可以自底向上填充DP表，其中dp[m][n]表示m个苹果n个盘子的分法数：
| M\N | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 2 | 2 |
| 3 | 1 | 2 | 3 | 3 |
| 4 | 1 | 3 | 4 | 5 |
填充规则：
- dp[0][n] = 1
- dp[m][1] = 1
- 当n > m时，dp[m][n] = dp[m][m]
- 否则，dp[m][n] = dp[m][n-1] + dp[m-n][n]
3.2 C++实现
int countWaysDP(int m, int n) { int dp[11][11] = {0}; // 初始化边界条件 for (int j = 1; j <= n; ++j) dp[0][j] = 1; for (int i = 1; i <= m; ++i) dp[i][1] = 1; for (int i = 1; i <= m; ++i) { for (int j = 2; j <= n; ++j) { if (j > i) { dp[i][j] = dp[i][i]; } else { dp[i][j] = dp[i][j-1] + dp[i-j][j]; } } } return dp[m][n]; }4. 空间优化与进阶思考
4.1 滚动数组优化
观察状态转移方程，当前行只依赖上一行和当前行前面的值，可将空间复杂度从O(M*N)优化到O(N)：
int countWaysOpt(int m, int n) { int dp[11] = {1}; // dp[0] = 1 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (j > i) continue; dp[j] += dp[j-i]; } } return dp[n]; }4.2 与其他DP问题的关联
放苹果问题实际上是完全背包问题的特例——背包容量为M，物品重量为1到M，每种物品无限个，求装满背包的组合数。其状态转移方程与以下经典问题同源：
- 整数划分：将正整数M表示为若干个正整数之和的方案数
- 硬币找零：用无限硬币凑出金额M的方法数
- 爬楼梯：每次爬1或2阶，到第M阶的方法数
4.3 变种问题扩展
- 盘子不同：如果盘子有区别，分法数为组合数C(M+N-1, N-1)
- 不允许空盘：先在每个盘放一个苹果，转化为M-N个苹果放N个盘子
- 苹果不同：每个苹果唯一，分法数为N^M（每个苹果有N种选择）
// 不允许空盘的解法 int countWaysNoEmpty(int m, int n) { if (m < n) return 0; return countWaysDP(m - n, n); }在解决实际项目中的资源分配问题时，我经常发现这些变种比原问题更常见。比如服务器集群的任务分配（相当于"不允许空盘"的变种），或者有优先级的任务调度（相当于"苹果不同"的情况）。