从‘放苹果’到‘数的划分’：一个动态规划思路如何搞定两道经典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)这与放苹果问题mn-k, nk的情况完全一致。这种问题归约的思维是算法设计的核心能力。提示在竞赛中遇到新问题时先问自己这个问题与我已知的哪个模型最相似2. 动态规划模型的构建与演变2.1 状态定义的通用模式对于这类划分问题动态规划的状态定义通常遵循以下模板dp[i][j]: 将i个单位划分为j个部分的方案数但具体实现时需要考虑边界条件的差异条件类型放苹果数的划分初始条件dp[0][j]1dp[0][0]1无效状态dp[i][j]0 (ij)dp[i][j]0 (ij)单容器/单部分dp[i][1]1dp[i][1]12.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) { vectorvectorint dp(m1, vectorint(n1, 0)); for(int i0; im; i) { for(int j1; jn; j) { if(i0 || j1) dp[i][j] 1; else if(ij) 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) { vectorvectorint dp(n1, vectorint(k1, 0)); dp[0][0] 1; for(int i1; in; i) { for(int j1; jk; j) { if(ij) dp[i][j] 0; else if(j1) 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) { vectorint dp(n1, 0); dp[0] 1; for(int j1; jk; j) { for(int ij; in; i) { dp[i] dp[i-j]; } } return dp[n]; }注意优化后的代码虽然节省空间但会丢失中间状态信息不适合需要回溯解的场景。4. 解题思维的进阶训练4.1 问题变种识别矩阵掌握基础模型后可以应对各种变种问题。下表总结了常见变种的特征变种特征对应解法调整例题参考各部分不同转换为组合问题洛谷P1025指定最小大小预处理减去最小值LeetCode 698限制最大部分增加状态维度Codeforces 111D输出具体划分增加回溯路径记录信息学奥赛一本通13044.2 思维训练方法论建立问题档案对每个经典问题记录核心模型边界条件常见变种与其他问题的关联定期做类比练习例如比较背包问题与硬币兑换比较最长公共子序列与编辑距离构建思维导图将算法问题按相似性分类形成知识网络graph LR A[划分问题] -- B[放苹果] A -- C[数的划分] A -- D[整数拆分] B -- E[允许空盘] C -- F[不允许空部分] D -- G[不考虑顺序]4.3 竞赛中的实战技巧快速识别问题类型看到题目先判断是否属于划分问题验证模型适用性检查题目约束是否匹配模型前提处理特殊边界特别注意n0, k0等极端情况测试样例设计构造包含以下情况的测试用例n kn kk 1最大边界值在NOIP等竞赛中这类问题的典型数据范围是n≤200k≤10因此O(nk)的解法完全足够。但在一些更高级别的比赛中可能需要更优化的解法。