1. 项目缘起从一道复试真题到算法思维的深度探索最近在整理一些高校计算机专业研究生复试的历年真题发现“东华复试100”系列里有一道关于“邮票”的题目讨论热度一直不低。这道题初看平平无奇甚至有点像小学数学题但真正动手去解才发现里面藏着不少门道。它不像那些直接考察复杂数据结构的算法题一眼就能看出要用动态规划或者图论这道“邮票题”更像是一个精巧的逻辑谜题考察的是将实际问题抽象为数学模型并设计高效求解算法的综合能力。很多同学卡在“暴力枚举超时”或者“状态设计冗余”的坑里这正是这道题的价值所在——它逼着你去思考如何用有限的计算机资源去解决一个理论上组合爆炸的问题。简单来说题目的核心是这样的给定若干种不同面值的邮票假设每种邮票数量无限我们需要用这些邮票来组成一个总面值。问题通常有两种问法一是求无法组成的最大连续整数经典的中国邮资问题或硬币问题变种二是给定一个目标值求最少的邮票张数。无论是哪种其本质都是“完全背包问题”或“无限背包问题”的变体但结合了连续性和最值优化使得它比标准的背包问题多了一层思考。我之所以花时间深入研究这道题是因为它在面试和机试中非常典型。它不要求你背诵某个生僻的算法而是实实在在地考察你的问题分析、建模和优化能力。接下来我将结合这道“东华复试100”中的邮票题拆解其核心思路分享从暴力搜索到动态规划再到各种剪枝和优化技巧的完整思考链路并附上可运行的代码和详细的调试心得。无论你是正在备战复试的同学还是想巩固动态规划基础的朋友相信这篇长文都能给你带来收获。2. 问题定义与经典变体分析在深入代码之前我们必须先把问题本身掰扯清楚。网络上流传的“邮票问题”版本很多容易混淆。我们以“东华复试100”中常见的描述为基准并厘清它的几个重要变体。2.1 标准问题描述假设我们有k种不同面值的邮票分别记为stamps[0], stamps[1], ..., stamps[k-1]。每种邮票都可以无限次使用。现在我们希望用这些邮票来粘贴信封组成不同的邮资。变体一求最大不可达连续邮资连续邮资问题这是最经典也是难度较高的一个变体。题目要求找出最大的整数N使得从1到N的所有邮资都能被组成而N1无法被组成。这个N就是最大连续邮资。例如假设邮票面值为{1, 3, 5}。邮资1可以用1分邮票。邮资2可以用11分邮票。邮资3可以用3分邮票。邮资4可以用13分邮票。邮资5可以用5分邮票。邮资6可以用15或33分邮票。邮资7可以用115或133分邮票。邮资8可以用35分邮票。邮资9可以用135分邮票。邮资10可以用55分邮票。邮资11可以用155分邮票。 此时我们发现邮资12似乎无法用{1,3,5}组成可以自己尝试。那么最大连续邮资N就是11因为1到11都能组成12不能。变体二求组成指定邮资的最少邮票张数这是更接近标准完全背包问题的描述。给定一个目标邮资T求用给定的无限邮票组成该邮资所需的最少邮票张数。如果无法组成则返回-1或特定标识。例如邮票面值{1, 3, 5}目标邮资T11。 最少张数是3例如155。这是一个典型的优化问题。变体三求组成指定邮资的所有可能方式数这是计数问题而非优化问题。给定目标邮资T求有多少种不同的邮票组合方式顺序不同视为同一种组合即不考虑排列。这涉及到动态规划中的“组合数”问题。“东华复试100”中考察的重点通常是变体一和变体二。尤其是变体一它不仅是动态规划还需要确定一个有效的搜索上界和状态定义对思维的要求更高。本文将重点讲解变体一最大连续邮资的求解因为理解了它变体二就迎刃而解了。2.2 问题抽象与难点识别为什么这个问题值得单独拿出来讲因为它有几个容易让人栽跟头的坑搜索空间无限大邮票无限理论上可以组成任意大的邮资。我们不可能从1开始无穷尽地尝试下去。如何确定一个合理的“上界”来停止搜索是第一个关键点。状态定义与转移对于“能否组成邮资i”这个问题最直观的想法是dp[i] true/false。但这对于求“最大连续”效率不高。更高效的做法是dp[i] 组成邮资i所需的最少邮票张数。这样dp[i]在有效时是一个正整数无效时我们可以用一个特殊值如无穷大INF表示。那么连续性的判断就变成了从1开始第一个dp[i]为INF的i其前一个i-1就是最大连续邮资N。初始化与边界条件dp[0]应该等于0组成0邮资需要0张邮票。这是所有动态规划问题的常见起点。对于每个邮票面值sdp[s]可以初始化为1如果s在面值集合中。算法复杂度假设我们确定的上界是M邮票种类为k那么标准的完全背包DP时间复杂度是O(k * M)。如何尽可能减小M是优化性能的核心。理清了问题和难点我们就可以着手设计解决方案了。我们将采取循序渐进的方式从最直观的暴力思路开始逐步优化到高效的动态规划解法。3. 核心算法设计从暴力DFS到动态规划很多同学的第一反应是深度优先搜索DFS或广度优先搜索BFS枚举所有可能的组合。这在小数据时可行但一旦数据量稍大就会立刻超时。我们来分析一下原因并引出正确的动态规划解法。3.1 暴力搜索为何行不通假设邮票面值为{1, 2}求最大连续邮资。用DFS的思路从邮资1开始尝试组成11组成211, 2组成3111, 12组成41111, 112, 22...你会发现随着邮资增大组合数呈指数级增长。这本质上是“整数拆分”问题。对于k种面值要判断邮资N是否可达最坏情况需要探索的路径数量是O(k^N)级别这是完全不可接受的。因此我们必须寻找一种能避免重复计算子问题的方法这正是动态规划的用武之地。3.2 动态规划状态定义与转移方程我们采用求解“变体二”最少邮票张数的动态规划方法来解决“变体一”最大连续邮资的问题。状态定义 设dp[i]表示组成邮资i所需的最少邮票张数。如果邮资i无法用给定的邮票组成则dp[i] INF一个很大的数如0x3f3f3f3f。状态转移方程 对于每一种邮票面值s我们都可以考虑在组成邮资(i - s)的基础上再加一张面值为s的邮票。因此状态转移方程为dp[i] min(dp[i], dp[i - s] 1)其中s遍历所有邮票面值且i - s 0。初始化dp[0] 0。这是动态规划的基石表示组成0元需要0张邮票。对于其他i (1 i M)dp[i] INF表示初始状态都不可达。然后对于每个邮票面值sdp[s] 1当然这也可以通过上面的转移方程在后续计算中得出显式初始化更清晰。求解最大连续邮资N 我们从i 1开始计算dp[i]直到遇到第一个dp[i] INF的i。那么i - 1就是我们要找的最大连续邮资N。但这里有一个核心问题M是多少我们该计算到哪个邮资为止总不能算到无穷大。3.3 确定动态规划的上界M这是一个关键的优化点。一个经典且有效的上界确定方法是如果当前可以连续组成邮资到N那么任何面值不大于N1的邮票都可以被纳入考虑来扩展连续范围。更具体的结论是这个结论需要理解而不是死记 设当前已知能连续组成的最大邮资为current_max初始为0。邮票面值数组已排序升序最小面值为min_stamp。 如果current_max min_stamp - 1那么我们可以尝试用现有邮票去更新更大的邮资。一个常用且安全的上界M可以设置为min_stamp * (目标值或某个足够大的数)但更精确的做法是迭代扩展。在实际编程中我们常采用一种动态扩展上界的策略设置一个初始上界M比如10000根据题目数据范围调整。在这个上界内进行DP计算。如果计算完成后发现从1到M的邮资全部可以组成即没有遇到dp[i]INF那么说明我们设置的上界M可能不够大需要扩大M重新计算。但这种情况在邮票包含面值1时只要M足够大就不会出现“全部连续”的情况因为总会有无法组成的数。如果邮票不含面值1则连续邮资可能有限。更稳妥的方法是我们一直计算直到连续中断找到dp[i]INF为止。但程序需要在一个有限循环内结束。一个经典且有效的上界公式是M min_stamp * (max_stamp 1)或M max_stamp * max_stamp。对于竞赛或复试题目数据范围通常会有提示比如邮资不超过10000。我们可以将M设为一个稍大的安全值例如20000。为了逻辑清晰我们假设题目给定了一个最大可能的邮资上限MAX_T比如10000。我们的DP数组就开到MAX_T 5。4. 代码实现与逐行解析理论说再多不如一行代码。下面我将给出用C实现求解“最大连续邮资”的完整代码并附上详细的注释。这里假设邮票面值包含1且我们寻找的上界是MAX_N。#include iostream #include vector #include algorithm #include cstring using namespace std; const int INF 0x3f3f3f3f; // 用一个很大的数代表“无穷大”表示不可达 const int MAX_N 10000; // 假设我们寻找的最大连续邮资不会超过10000 int main() { int k; // 邮票种类数 cout 请输入邮票种类数 k: ; cin k; vectorint stamps(k); cout 请输入 k 种邮票的面值: ; for (int i 0; i k; i) { cin stamps[i]; } // 对邮票面值进行排序虽然不是必须但有时有助于理解或某些优化 sort(stamps.begin(), stamps.end()); // 初始化DP数组dp[i]表示组成邮资i所需的最少邮票数初始为无穷大 vectorint dp(MAX_N 1, INF); dp[0] 0; // 边界条件组成0元需要0张邮票 // 完全背包DP过程 // 注意这里遍历邮资i从1到MAX_N for (int i 1; i MAX_N; i) { for (int s : stamps) { // 遍历每一种邮票 if (i - s 0 dp[i - s] ! INF) { // 如果邮资i-s可以被组成那么邮资i就可以在它的基础上加一张面值s的邮票组成 // 我们取所有可能方案中的最小值 dp[i] min(dp[i], dp[i - s] 1); } } } // 寻找最大连续邮资N int maxContinuous 0; for (int i 1; i MAX_N; i) { if (dp[i] INF) { // 找到第一个无法组成的邮资 maxContinuous i - 1; // 它的前一个就是最大连续邮资 break; } // 如果循环结束都没找到INF说明在MAX_N范围内全部连续那么最大连续邮资就是MAX_N // 但根据问题性质如果邮票不含面值1这是可能的。如果含面值1则MAX_N需要足够大。 if (i MAX_N) { maxContinuous MAX_N; } } cout 最大连续邮资 N 为: maxContinuous endl; // 附加输出可以打印出前若干邮资的组成情况以供验证 cout \n--- 邮资组成详情前30项--- endl; for (int i 1; i min(30, maxContinuous 5); i) { if (dp[i] ! INF) { cout 邮资 i - 最少需要 dp[i] 张邮票 endl; } else { cout 邮资 i - 无法组成 endl; } } return 0; }代码关键点解析dp数组初始化vectorint dp(MAX_N 1, INF)创建了大小为MAX_N1的数组并全部填充为INF。dp[0] 0是动态规划正确的起点。双重循环顺序外层循环i遍历所有待求的邮资从1到MAX_N。内层循环s遍历所有邮票面值。这个顺序是“对于每个邮资尝试所有邮票”是标准的完全背包问题解法。它与“对于每种邮票遍历所有邮资”的顺序在完全背包中是等价的但前者更直观。状态转移条件if (i - s 0 dp[i - s] ! INF)是核心。首先确保索引不越界i-s非负其次确保子问题i-s是有解的可达。只有满足这两个条件我们才能尝试用dp[i-s] 1来更新dp[i]。寻找最大连续邮资在DP计算完成后我们线性扫描dp数组。找到第一个值为INF的索引i那么i-1就是答案。这个扫描过程是O(MAX_N)的效率很高。上界MAX_N的选取这是代码中的一个假设。在实际题目中需要根据数据范围来定。如果题目说“结果保证小于10000”那么MAX_N10000是安全的。如果没给可能需要设置得更大或者采用更智能的终止判断例如如果连续找到很长一段都可达可以合理推测后续也连续但这不是绝对可靠的。5. 实例演算与调试技巧让我们用代码实际跑几个例子并看看在调试过程中如何观察状态变化。实例一邮票面值 {1, 3, 5}运行程序输入k3面值1 3 5。 程序输出最大连续邮资N为11。 查看详情前30项你会发现邮资12显示“无法组成”。这与我们手动分析的结果一致。实例二邮票面值 {1, 4, 7}运行程序输入k3面值1 4 7。 输出最大连续邮资N为17。我们来验证一下能组成1,2(11),3(111),4,5(41),6(411),7,8(71),9(711),10(7111?), 等等。手动验证17是可组成的例如77111而18似乎无法组成。结论正确。调试技巧打印DP表在初学或调试时将DP数组的关键部分打印出来是理解算法运行过程的最佳方式。例如在计算完DP后可以打印出dp[0]到dp[20]的值i : dp[i] 0 : 0 1 : 1 2 : 2 3 : 1 4 : 2 5 : 1 6 : 2 7 : 3 8 : 2 9 : 3 10: 2 11: 3 12: INF 13: INF ...看到dp[12] INF就一目了然地知道邮资12无法组成。这种可视化方法对于验证算法正确性和理解状态转移至关重要。常见错误排查数组越界确保i - s 0的判断不能省略否则会访问dp数组的负索引导致运行时错误或不可预知的行为。初始化错误忘记将dp[0]设置为0会导致所有状态都无法转移因为所有状态都试图从dp[0]转移过来。结果就是所有dp[i]都是INF。INF值设置过小如果邮票张数可能很多dp[i]的值可能很大。如果INF设置得不够大比如只设置了10000而在状态转移中dp[i - s] 1可能超过这个值导致min操作出错。通常用0x3f3f3f3f约10^9对于竞赛题目是安全的。上界MAX_N不足如果实际的最大连续邮资大于你设置的MAX_N程序会错误地输出MAX_N作为结果。解决方法是根据题目数据范围合理设置MAX_N或者实现更智能的终止判断逻辑例如如果连续找到超过最小面值倍的数都可达可以提前终止但这需要数学证明。6. 性能优化与进阶思考上面的解法时间复杂度是O(k * MAX_N)空间复杂度是O(MAX_N)。对于MAX_N10000, k20的典型复试题目这已经绰绰有余。但如果我们想挑战更大数据量或者深入理解问题还有一些优化和进阶方向。6.1 滚动数组优化空间注意到状态转移方程dp[i] min(dp[i], dp[i - s] 1)中dp[i]只依赖于dp[i - s]其中i - s i。而且在内层循环中我们正序更新dp[i]。这实际上是完全背包的标准形式。对于完全背包我们可以优化掉第一维物品维度只使用一维数组并且内层循环遍历邮资需要正序。我们的代码已经使用了一维数组并且是正序更新所以已经是空间优化后的版本了。这一点需要理解正是因为每种邮票无限使用完全背包我们才能在当前轮次中使用刚刚更新过的dp[i - s]它可能已经包含了使用当前邮票s的结果来更新dp[i]。这与01背包每种物品只能用一次需要逆序更新是不同的。6.2 算法正确性证明与上界严格推导我们之前设置MAX_N是一种工程上的安全做法。从数学上对于一组包含面值1的邮票最大连续邮资是否一定存在如果存在是否有办法确定一个更精确的上界避免无用的计算结论是如果邮票中包含面值1那么无法组成的邮资一定存在因为邮票种类有限面值固定。一个经典的上界是min_stamp * max_stamp具体形式可能有变种如(min_stamp - 1) * max_stamp - 1。其背后的思想是“Frobenius Coin Problem”的推广。对于只有两种面值a, b互质的情况最大不可表示整数是a*b - a - b。对于更多种面值问题更复杂但min_stamp * max_stamp常作为一个实用的宽松上界。在实际编程中如果题目没有给出明确范围我们可以采用一种“动态探测”的方法设置一个较大的初始上界limit如1000000。进行DP计算。同时维护一个计数器consecutive记录当前连续可达的邮资长度。如果consecutive超过了min_stamp或max_stamp的若干倍例如100倍我们可以合理推断后续可能全部连续对于含面值1的情况这推断不成立但对于不含面值1的情况可能成立或者直接以当前limit作为搜索范围。更严谨的做法是依赖数学结论设定上界。6.3 变体二求最少邮票张数的直接应用我们的dp数组本身存储的就是组成邮资i的最少邮票张数。因此求解“给定目标邮资T的最少张数”易如反掌。只需要在计算完DP数组后查询dp[T]即可。如果dp[T] INF则输出-1或“无法组成”。int target; cout 请输入目标邮资: ; cin target; if (dp[target] ! INF) { cout 组成邮资 target 最少需要 dp[target] 张邮票。 endl; } else { cout 无法组成邮资 target endl; }6.4 如果邮票数量有限多重背包这是一个更有挑战性的变体。如果每种邮票s不是无限张而是有给定的数量count[s]那么问题就变成了“多重背包问题”。状态转移方程需要稍作修改我们仍然定义dp[i]为组成邮资i所需的最少邮票张数或是否可达。但是在更新时对于每种邮票s我们需要考虑使用0张、1张、...、count[s]张的情况。最直接的方法是将其转化为01背包问题将每种有c个的物品拆分成c个独立的物品但这样当c很大时效率低下。标准的优化方法是使用“二进制拆分”或“单调队列优化”。不过在复试笔试或面试中如果数据量不大直接转化为01背包或者使用三重循环遍历邮资、遍历邮票种类、遍历该邮票的使用张数也是可以接受的。三重循环示例伪代码for (int i 1; i MAX_N; i) { for (int j 0; j k; j) { int s stamps[j]; int cnt counts[j]; // 第j种邮票的数量 for (int use 1; use cnt i - use * s 0; use) { if (dp[i - use * s] ! INF) { dp[i] min(dp[i], dp[i - use * s] use); } } } }这种方法时间复杂度较高O(MAX_N * k * 平均数量)仅适用于小数据量。7. 总结与个人实战心得这道“邮票问题”虽然归类在“东华复试100”中但它所考察的动态规划思想是通用的是背包问题的一个非常经典的变体。通过这个问题的深入剖析我们实际上串联起了以下几个关键知识点问题抽象能力将“贴邮票”这个生活问题准确抽象为“给定面值集合求连续可组成整数范围”的数学模型。动态规划状态设计dp[i]定义为“最少张数”而非简单的“是否可达”是一个关键的优化它让后续求最大连续值变得简单直接。完全背包的遍历顺序理解为什么内层循环正序更新是解决“无限使用”问题的关键这与01背包的逆序更新形成对比。边界条件与初始化dp[0] 0是几乎所有类似DP问题的起点务必牢记。算法效率与上界分析在竞赛或面试中能对算法的时间/空间复杂度进行分析并对不确定的上界给出合理的估计和解释是加分项。在我自己实现和调试的过程中最大的收获有两点 一是一定要手动模拟小数据。比如用{1,3,5}这个例子在纸上画出dp数组的前十几项值能极大地帮助你理解状态是如何转移的以及你的代码逻辑是否正确。 二是重视调试输出。不要只盯着最终结果。把关键的中间状态如dp数组片段打印出来是定位BUG最快的方法。很多逻辑错误比如数组越界、初始化遗漏通过观察中间状态都能一眼看出。最后这道题还可以有很多扩展比如求具体的组合方案而不仅仅是张数或者像“硬币找零”问题一样求所有组合方式的数量。其核心动态规划框架都是相似的只是状态定义和转移方程需要相应调整。掌握了这个核心框架再遇到类似的“组合优化”问题你就能更快地识别出模型并套用解题思路了。