从‘放苹果’到‘数的划分’：一个动态规划思路如何搞定两道经典OJ题（附C++代码）
从‘放苹果’到‘数的划分’：动态规划思维的迁移艺术
第一次在算法竞赛中遇到"数的划分"问题时，我盯着题目描述足足十分钟毫无头绪——直到突然想起之前做过的"放苹果"问题。这种灵光乍现的瞬间，正是算法学习中最为珍贵的顿悟时刻。本文将带你深入剖析这两道经典题目背后的思维联系，掌握动态规划模型迁移的核心技巧，而不仅仅是记住几个状态转移方程。
1. 问题本质的类比思考
1.1 表面差异下的共同结构
"放苹果"和"数的划分"乍看是两类不同的问题：
- 放苹果问题：将m个相同的苹果放入n个相同的盘子，允许空盘，求分配方法数
- 数的划分：将整数n划分为k个正整数之和，求划分方法数
但当我们用组合数学的眼光审视时，会发现它们本质都是划分相同物品到相同容器的问题。关键差异仅在于一个约束条件：
# 问题约束对比 放苹果：每个盘子 ≥0 个苹果 数的划分：每个部分 ≥1 个单元1.2 模型转换技巧
通过简单的变量代换就能建立等价关系。设数的划分中每个数为aᵢ，则有：
n = a₁ + a₂ + ... + aₖ (aᵢ ≥1)令bᵢ = aᵢ -1，则转化为：
n-k = b₁ + b₂ + ... + bₖ (bᵢ ≥0)这与放苹果问题m=n-k, n=k的情况完全一致。这种问题归约的思维是算法设计的核心能力。
提示：在竞赛中遇到新问题时，先问自己"这个问题与我已知的哪个模型最相似？"
2. 动态规划模型的构建与演变
2.1 状态定义的通用模式
对于这类划分问题，动态规划的状态定义通常遵循以下模板：
dp[i][j]: 将i个单位划分为j个部分的方案数但具体实现时需要考虑边界条件的差异：
| 条件类型 | 放苹果 | 数的划分 |
|---|---|---|
| 初始条件 | dp[0][j]=1 | dp[0][0]=1 |
| 无效状态 | dp[i][j]=0 (i<j) | dp[i][j]=0 (i<j) |
| 单容器/单部分 | dp[i][1]=1 | dp[i][1]=1 |
2.2 状态转移方程的推导
两种问题的状态转移都基于最后一部分是否为空的决策：
放苹果的转移方程：
dp[i][j] = dp[i][j-1] + dp[i-j][j]解释：
dp[i][j-1]：至少一个盘子为空dp[i-j][j]：所有盘子至少一个苹果
数的划分的转移方程：
dp[i][j] = dp[i-1][j-1] + dp[i-j][j]解释：
dp[i-1][j-1]：至少一个部分为1dp[i-j][j]：所有部分≥2
关键区别在于第一个项的处理，这反映了空盘与非空盘的约束差异。
3. 代码实现与优化技巧
3.1 基础实现对比
放苹果的标准解法：
int countApple(int m, int 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 || j==1) dp[i][j] = 1; else if(i<j) dp[i][j] = dp[i][j-1]; else dp[i][j] = dp[i][j-1] + dp[i-j][j]; } } return dp[m][n]; }数的划分的标准解法：
int countPartition(int n, int k) { vector<vector<int>> dp(n+1, vector<int>(k+1, 0)); dp[0][0] = 1; for(int i=1; i<=n; ++i) { for(int j=1; j<=k; ++j) { if(i<j) dp[i][j] = 0; else if(j==1) dp[i][j] = 1; else dp[i][j] = dp[i-1][j-1] + dp[i-j][j]; } } return dp[n][k]; }3.2 空间优化策略
两种问题都可以使用滚动数组优化空间复杂度到O(n)：
int countPartition(int n, int k) { vector<int> dp(n+1, 0); dp[0] = 1; for(int j=1; j<=k; ++j) { for(int i=j; i<=n; ++i) { dp[i] += dp[i-j]; } } return dp[n]; }注意：优化后的代码虽然节省空间，但会丢失中间状态信息，不适合需要回溯解的场景。
4. 解题思维的进阶训练
4.1 问题变种识别矩阵
掌握基础模型后，可以应对各种变种问题。下表总结了常见变种的特征：
| 变种特征 | 对应解法调整 | 例题参考 |
|---|---|---|
| 各部分不同 | 转换为组合问题 | 洛谷P1025 |
| 指定最小大小 | 预处理减去最小值 | LeetCode 698 |
| 限制最大部分 | 增加状态维度 | Codeforces 111D |
| 输出具体划分 | 增加回溯路径记录 | 信息学奥赛一本通1304 |
4.2 思维训练方法论
建立问题档案：对每个经典问题记录：
- 核心模型
- 边界条件
- 常见变种
- 与其他问题的关联
定期做类比练习：例如：
- 比较"背包问题"与"硬币兑换"
- 比较"最长公共子序列"与"编辑距离"
构建思维导图：将算法问题按相似性分类，形成知识网络
graph LR A[划分问题] --> B[放苹果] A --> C[数的划分] A --> D[整数拆分] B --> E[允许空盘] C --> F[不允许空部分] D --> G[不考虑顺序]4.3 竞赛中的实战技巧
- 快速识别问题类型：看到题目先判断是否属于划分问题
- 验证模型适用性：检查题目约束是否匹配模型前提
- 处理特殊边界：特别注意n=0, k=0等极端情况
- 测试样例设计：构造包含以下情况的测试用例：
- n < k
- n = k
- k = 1
- 最大边界值
在NOIP等竞赛中，这类问题的典型数据范围是n≤200，k≤10，因此O(nk)的解法完全足够。但在一些更高级别的比赛中，可能需要更优化的解法。