1. 从 1231 这组样例出发为什么暴力枚举会被卡死在信息学奥赛一本通的动态规划章节里编号 1275 的【例9.19】乘积最大是一道被无数人反复讲、又反复讲错的题。它出自早年的 NOIP 提高组题面朴素得像小学奥数给一个长度为 N 的数字串再给 K 个乘号要求把这 K 个乘号全部插进数字串的缝隙里使分出来的 K1 个部分相乘的结果最大。这道题的输入只有两行输出只有一个整数看起来五分钟就能写完但真正动手的人很快会发现两个问题一是怎么切才最优靠人眼试根本试不出来二是当 N 最大到 40 的时候答案会膨胀到 40 位以上用long long存结果直接溢出。这篇内容我不打算只贴一份代码就完事。和平常写题解不一样我更想把为什么状态要这么定义为什么枚举范围只能这么取为什么高精度不是可选优化而是必需品这几件事说透。因为把这道题吃下来你顺手就能拿下后面一大类区间决策类的问题投入产出比很高。1.1 三个容易读漏的题目约束先把题目条件逐条罗列清楚这三条里任何一条看漏代码都过不了。第一乘号必须恰好用完。题目说的是使用 K 个乘号不是至多 K 个。这意味着分出来的段数固定是 K1 段每一段至少得有 1 位数字。这是后面枚举范围推导的直接依据。第二数字串的长度 N 可能到 40。数据范围大致是 6 ≤ N ≤ 401 ≤ K ≤ 6且 K N。40 位数字切 7 段最后乘积的量级在 10 的 40 次方上下而long long的极限只有约 9.2 × 10 的 18 次方连尾数都比不上。所以这道题的正解必须自带高精度。第三数字串里可能出现 0。很多人在写状态初值的时候习惯用-1表示这个状态还没被算过结果遇到含 0 的数据就翻车——因为真实的乘积就是 0跟你用来表示未计算的哨兵值撞车了。这个坑我在后面会单独说。样例输入是4 2加一行1231样例输出是62。切法是1 * 2 * 31。你可以自己验算一下其他两种切法1 * 23 * 1 2312 * 3 * 1 36确实都不如 62。1.2 让两段尽量匀的直觉为什么一定会错大部分人第一次做这道题脑子里会冒出一个贪心既然要让乘积最大那让每一段的数值尽量接近不就行了这就是小学里和一定、差越小积越大的直觉。这个直觉在两个数的场合是对的但一旦段数变多、而且还要考虑数位长度对数值的影响它就完全失效了。举个能直接打脸的例子数字串1119K 1也就是只切一刀。三种切法分别是 1 × 119 119、11 × 19 209、111 × 9 999。按尽量匀的直觉应该选 11 × 19 209但真实最优是 111 × 9 999差了将近五倍。为什么会这样因为在这个数字串里末位那个 9 是唯一的大数因子把它单独切出来当乘数收益远大于让两段位数接近。数字的大小是由高位主导的而位数接近只是看起来匀跟数值均衡完全是两码事。更有意思的是同一组数字串在不同 K 下最优切点会跳到完全不同的位置。还是1231K 1 时最优是12 * 31 372切在中间K 2 时最优却是1 * 2 * 31 62切在靠前的位置。同一串数字乘号个数一变最优结构就变了。这就说明不存在一个固定的贪心规则能覆盖所有情况必须老老实实做决策搜索。1.3 枚举所有切法的代价C(39,6) 不是一个小数字有人会想那我把所有切法枚举一遍不就行了N 40 的时候一共有 39 个空隙从中选 K 6 个位置放乘号组合数是 C(39, 6) 3262623三百多万种。单看这个数字好像还在可接受范围内——如果每次切分只需要一次整数乘法的话确实如此。但问题恰恰在于每一次切分你都要做 6 次高精度乘法而每个大数可能有 40 位左右。手写大数乘法是 O(L²) 的L ≈ 40一次就是 1600 次基本运算6 次乘法加起来接近一万次。总运算量大约是 3262623 × 10000 ≈ 3.3 × 10 的 10 次方这个量级在竞赛的 1 秒时限里是绝对过不去的。而用动态规划来做需要执行的乘法次数只有几千次——具体来说是三层循环枚举状态和决策点的组合数大概是 K × N² / 2 ≈ 4800 次。从三千万次运算降到五千次这就是为什么这道题必须用 DP而不是靠枚举加剪枝硬扛。2. dp[i][j] 这个状态不是拍脑袋定的动态规划最难的从来不是写转移方程而是想清楚状态该怎么定义。很多人背下了这道题的dp[i][j]表示前 i 个数字里插 j 个乘号但问他为什么这么定答不上来。我把自己当初推导的过程完整复述一遍希望能帮你建立状态是被问题结构逼出来的这种感觉。2.1 决策动作到底是选数字还是切位置很多人一看到乘积最大第一反应是把状态定义成选到第几个数字为止然后纠结于这个数字到底属于哪一段。这就是走偏了。重新读一遍题目数字串的顺序是不能打乱的你能做的唯一动作就是在某些缝隙里插入乘号。所以真正意义上的决策是第 i 个数字后面到底切不切。换句话说问题的解是一组切分位置的集合而不是一组数字的排列。一旦意识到决策对象是切分点状态的形状就清晰了我们需要记录的核心信息是已经处理到了数字串的第几位以及已经用掉了几个乘号。前者决定了还剩哪些数字可用后者决定了还剩几个乘号要放。这两个维度合起来就组成了dp[i][j]。2.2 为什么按前缀长度的划分天然满足无后效性动态规划能不能成立关键看状态转移有没有后效性。所谓无后效性就是一旦到达某个状态未来的决策只跟这个状态本身有关跟你是怎么走到这里的无关。对于这道题dp[i][j]表示把前 i 个数字分成 j1 段的最大乘积。注意这里的关键点前 i 个数字被划分成 j1 段之后后面剩下的数字串第 i1 位到第 N 位该怎么切跟前面这 j1 段具体是怎么分的没有关系。因为你只需要知道前面那部分的最大乘积是多少后面部分的最优切法不受影响它们之间唯一的耦合就是乘起来这个动作。这就满足了最优子结构全局最优解一定能拆成一个前缀最优解乘上一段后缀数字。反过来说如果你把状态定义成第 i 个数字所在的段是从第几位开始的那状态的维度就爆炸了而且也不满足无后效性因为后续切分要依赖的具体分段信息太多了。2.3 初始化dp[i][0] 与无解状态的处理选择状态定好之后边界条件就顺理成章了。dp[i][0]表示前 i 个数字里一个乘号都不放那就只有一个段值就是前 i 位数字组成的那个整数。比如样例里的1231dp[1][0] 1dp[2][0] 12dp[3][0] 123dp[4][0] 1231。这个初始化用高精度直接对字符串切片转换就行非常直观。至于无解状态有两种常见写法。一种是把整个 dp 数组初始化为 0因为乘积的最小可能值就是 00 作为一个合法的当前最大候选值不会造成任何错误——任何正数都会把它顶掉而如果所有候选都算出来是 0那说明数字串里全是 0答案本来就是 0。另一种是初始化为 -1 当作哨兵转移时特判。我强烈建议第一种理由很实在这题的乘积天然是非负的0 本身就是合法值域的下界用它当初始值既省代码又不会误判而 -1 哨兵反而会在含 0 的数据上制造歧义。这里还有个容易忽略的细节dp[i][j]只对 j i 有意义。因为要把前 i 个数字切成 j1 段每段至少 1 位所以必须满足 i ≥ j1。对于 i ≤ j 的状态我们根本不会去访问也就不用管。3. 转移方程里枚举点 t 的上下界写错一个就 WA转移方程本身不长但那个枚举变量的取值范围是这道题最容易写错的地方。我见过太多人把下界写成 1结果要么数组越界要么算出莫名其妙的答案。3.1 把最后一段单独拎出来推导转移方程的标准姿势是思考最后一步做了什么决策。当我们计算dp[i][j]前 i 个数字插 j 个乘号分成 j1 段时考虑最后一个乘号插在哪里。假设它插在第 t 个数字之后那么整个串就被切成了两部分前面是前 t 个数字后面是从第 t1 位到第 i 位的这一段。前面那部分需要插 j-1 个乘号也就是dp[t][j-1]后面那部分是固定的一个整数记为num(t1, i)。于是转移方程就是dp[i][j] max{ dp[t][j-1] * num(t1, i) }对所有合法的 t 取最大值这里的num(t1, i)表示数字串从第 t1 位到第 i 位组成的那个整数。整个思路就是把最后一段的起点在哪里枚举一遍这是所有区间分割类 DP 的通用套路。3.2 下界为什么是 j 而不是 1现在来说枚举范围。t 的取值范围必须是[j, i-1]这两个边界都有明确的现实含义。先说下界 t ≥ j。因为dp[t][j-1]要求把前 t 个数字分成 j 段插 j-1 个乘号而分成 j 段至少需要 j 个数字。如果 t j这个状态根本没有意义强行访问会读到未初始化的垃圾值在 C 里就是默认的 0会让答案偏小。这就是为什么下界是 j而不是想当然的 1。再说上界 t ≤ i-1。因为最后一段num(t1, i)至少要包含 1 位数字所以 t 最多到 i-1。如果写成 t ≤ i那就切出一段空的num(i1, i)在字符串上是个非法区间转换出来直接错。顺带说一句外层循环的顺序必须是先枚举 j再枚举 i。因为dp[i][j]依赖的是dp[t][j-1]也就是乘号个数少一层的状态。只有当所有 j-1 层的结果都算完了才能算第 j 层。3.3 手推 1231 的完整 DP 表光看公式还是虚我们拿样例1231、K 2 手动跑一遍把整张表填出来。数字串各位分别是 1、2、3、1。先算所有区间数值num(1,1)1num(2,2)2num(3,3)3num(4,4)1num(1,2)12num(2,3)23num(3,4)31num(1,3)123num(2,4)231num(1,4)1231。i前 i 位dp[i][0]dp[i][1]dp[i][2]11——2122—31233664123137262逐格解释一下第 1 层j 1的计算dp[2][1]t 只能取 1dp[1][0] * num(2,2) 1 * 2 2。dp[3][1]t 取 1 得1 * num(2,3) 1 * 23 23t 取 2 得dp[2][0] * num(3,3) 12 * 3 36。取最大值 36。dp[4][1]t 取 1 得1 * 231 231t 取 2 得12 * 31 372t 取 3 得123 * 1 123。取最大值 372。再看第 2 层j 2注意此时 t 的下界是 2dp[3][2]t 只能取 2dp[2][1] * num(3,3) 2 * 3 6。dp[4][2]t 取 2 得dp[2][1] * num(3,4) 2 * 31 62t 取 3 得dp[3][1] * num(4,4) 36 * 1 36。取最大值 62。最终答案dp[4][2] 62跟样例输出完全对上。把这个表亲手推一遍比看十遍方程都管用——你能亲眼看到 t 的下界是怎么随着 j 往上走的。4. 40 位数字的乘积有多大高精度不是可选项前面提到高精度这里展开讲清楚为什么这道题绕不过去以及手写大数到底要写哪些东西。4.1 量级估算为什么 long long 一定会炸先做一个粗算让你对答案的大小有个概念。N 40、K 6也就是把 40 位数字切成 7 段。根据分段越均匀乘积越大的规律这个是针对位数成立的经验规律和前面说的数值均衡不一样7 段大致是每段 5 到 6 位。假设数字串里全是 940 位切 7 段比较合理的分法是 6666655 40。每段的数值大概在 10 的 5 次方到 10 的 6 次方之间7 段乘起来量级大约是 10 的 40 次方左右。这意味着答案有 40 位左右的十进制数字。long long能表示的最大值约是 9.22 × 10 的 18 次方也就是 19 位十进制数。两者差了二十多个数量级用long long存这个答案连中间过程都走不完第一次乘法就会溢出成负数或者垃圾值。4.2 C 手写大数乘法与比较的骨架C 没有任何内置大数必须手写。好在这道题只需要两个操作大数乘大数和大数比较大数。我一般用低位在前的数组存十进制位也就是d[0]存个位d[1]存十位以此类推。这样进位的时候从下标 0 往大走写起来最顺手。大数比较的逻辑很简单先比位数位数多的更大位数相同就从高位往低位逐位比第一位不同的谁大谁就大。这里有个非常经典的错误就是只写位数不同时比位数位数相同就返回相等——位数相同但数值不同的情况多了去了比如 1234 和 4321 都是 4 位必须逐位比较才能分出大小。大数乘法的核心是模拟竖式两层循环把d[i] * d[j]累加到结果的第ij位上等所有位都累加完再从低位到高位统一处理进位。中间累加用的数组要开得足够大长度份应该是两个乘数位数之和再加 2。关于中间值会不会溢出这里可以放心每一位的乘积最大是 9 × 9 81而同一位置上最多累加 40 次也就是 3240 左右int完全装得下。所以中间数组用int就够不需要long long。从字符串转大数也有个小讲究。我习惯用逐位乘 10 加当前位的方式从左到右扫字符串每读一位就把当前大数整体乘 10 再加上这一位的数字。这个过程中要用一个carry变量从低位往高位传递逻辑和乘法进位一样。特别注意全为 0 的输入因为 0 乘 10 还是 0没有产生任何进位数组长度会一直是 0必须特判——如果扫完了长度还是 0就把值设成 0、长度设成 1。4.3 Python 与 Java 的降维写法如果你只是想把这道题的思路搞明白而不是非得在 C 里手写高精度那用 Python 写这道题简直是降维打击。Python 的整数是任意精度的int直接就能存 40 位、甚至 1000 位的数乘法和比较都是原生支持的。同样一段 DP 逻辑Python 版本连大数类都不用写字符串转整数直接int(s[i-1:j])搞定十几行代码就能 AC。Java 的话java.math.BigInteger提供了multiply和compareTo两个方法也能省掉手写高精度的功夫只是写起来比 Python 啰嗦一些。不过我还是建议你至少手写一遍 C 版本。原因很现实竞赛的默认语言还是 C遇到真正卡高精度的题目你总得会写。Python 版本适合用来验证你的 DP 逻辑对不对——如果 Python 过了而 C 不过那问题一定出在高精度实现上排查方向一下子就清晰了。这里补充一句复杂度分析方便你判断自己的实现会不会超时。整个 DP 的乘法调用次数约为 K × N² / 2在 K 6、N 40 时大约是 4800 次每次大数乘法是 O(L²)L 最多 80 位左右也就是几千次基本运算。乘起来大概三千多万次基本操作在 C 里是毫秒级的完全不用担心性能。5. 完整代码与调试现场我在下标上栽的三个跟头代码我给两个版本C 的手写高精度版和 Python 的直球版。给完之后重点说说我当年调试时踩过的坑这几处比代码本身更值钱。5.1 C 版本数组存大数 手写乘法#include bits/stdc.h using namespace std; const int MAXL 105; struct Big { int d[MAXL]; // d[0] 是个位下标越大位权越高 int len; Big() { memset(d, 0, sizeof(d)); len 1; } // 默认值是 0 }; // 把 s[l..r] 转成大数下标从 0 开始闭区间 Big toBig(const string s, int l, int r) { Big a; a.len 0; for (int i l; i r; i) { int carry s[i] - 0; // a a * 10 当前位 for (int j 0; j a.len; j) { int t a.d[j] * 10 carry; a.d[j] t % 10; carry t / 10; } while (carry 0) { a.d[a.len] carry % 10; carry / 10; } } if (a.len 0) { a.d[0] 0; a.len 1; } // 全 0 的特判 return a; } Big mul(const Big a, const Big b) { Big c; if ((a.len 1 a.d[0] 0) || (b.len 1 b.d[0] 0)) return c; int tmp[MAXL * 2] {0}; for (int i 0; i a.len; i) for (int j 0; j b.len; j) tmp[i j] a.d[i] * b.d[j]; int len a.len b.len 1; for (int i 0; i len; i) { tmp[i 1] tmp[i] / 10; tmp[i] % 10; } while (len 1 tmp[len - 1] 0) --len; c.len len; for (int i 0; i len; i) c.d[i] tmp[i]; return c; } bool bigger(const Big a, const Big b) { // a b 吗 if (a.len ! b.len) return a.len b.len; for (int i a.len - 1; i 0; --i) if (a.d[i] ! b.d[i]) return a.d[i] b.d[i]; return false; } int n, k; string s; Big dp[45][10]; Big num[45][45]; int main() { cin n k; cin s; for (int i 0; i n; i) for (int j i; j n; j) num[i][j] toBig(s, i, j); for (int i 1; i n; i) dp[i][0] num[0][i - 1]; for (int j 1; j k; j) for (int i j 1; i n; i) for (int t j; t i - 1; t) { Big cand mul(dp[t][j - 1], num[t][i - 1]); if (bigger(cand, dp[i][j])) dp[i][j] cand; } for (int i dp[n][k].len - 1; i 0; --i) cout dp[n][k].d[i]; cout \n; return 0; }代码里num[t][i-1]这个下标最容易看晕dp里用的是前 i 位这种 1 起始的计数而num数组和字符串都是 0 起始的。前 i 位对应字符串下标0..i-1前 t 位对应0..t-1所以最后一段就是从下标 t 到 i-1写成num[t][i-1]。这个问题我在下一节会专门说。5.2 Python 版本n, k map(int, input().split()) s input().strip() # num[i][j]第 i 位到第 j 位组成的整数1 起始的闭区间 num [[0] * (n 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(i, n 1): num[i][j] int(s[i - 1:j]) dp [[0] * (k 1) for _ in range(n 1)] for i in range(1, n 1): dp[i][0] num[1][i] for j in range(1, k 1): for i in range(j 1, n 1): for t in range(j, i): dp[i][j] max(dp[i][j], dp[t][j - 1] * num[t 1][i]) print(dp[n][k])两边对照着看能明显感觉到 Python 把所有高精度的脏活都藏起来了剩下的骨架跟 C 一模一样。建议你先用 Python 把逻辑跑通再用 C 重写一遍这样调试的时候能确定问题到底是出在算法还是出在高精度实现上。5.3 三个真实踩坑记录坑一num 数组的下标基准混用。我当初写 C 版本的时候dp用的是 1 起始前 i 位结果在取最后一段的时候顺手写成了num[t 1][i]按照 Python 那套 1 起始的约定来写的。但 C 里num存的是 0 起始的字符串切片num[t1][i]实际取到的是从下标 t1 到 i 的内容正好错开了一位。表现就是样例能过因为位数少错位不太明显但交上去大面积 WA。这种错误的排查方法很简单打印中间状态把所有dp[i][0]打出来跟手算的前缀数值对一下一眼就能看出来错位。坑二大数比较只比长度。这是我见过最高频的高精度错误。很多人写比较函数的时候图省事只写了if (a.len ! b.len) return a.len b.len; return false;长度相同就直接认为相等。这在本题里会直接导致答案偏小因为两个位数相同的候选乘积会互相顶掉最后留下的可能不是真正最大的那个。正确写法必须是长度相同时逐位从高位往下比。坑三乘法中间数组没清空、或者开小了。中间数组tmp每次调用乘法都要重新清零如果把它写成全局变量或者static上一次的结果会残留下来污染这一次的计算。另外数组长度也要留够两个 40 位大数相乘结果最多 80 位进位之后可能到 81 位所以我习惯开MAXL * 2也就是 210稳一点。还有一个不算坑但值得提的点输出大数的时候千万别忘了逆序。因为数组是低位在前的d[0]是个位输出必须从len-1往下走到 0。写成从 0 到len-1输出的话你会看到一个数字完全反过来的答案。6. 换个问法这道题还能怎么变形把这道题的正解写出来只是第一步。真正让这道题的价值翻倍的是它背后那一套区间分割 决策枚举的思维能直接迁移到一大批变体上。这里挑几个最有代表性的说说。6.1 至多 K 个乘号多一层取 max 就够如果题目改成至多使用 K 个乘号答案就不是dp[n][K]了而是max(dp[n][0], dp[n][1], ..., dp[n][K])。为什么因为多用一个乘号并不总是更好。举个极端的例子数字串10、K 1切一刀得到1 * 0 0不切得到10。显然不切更优。原因是数字串里出现了 0任何跟 0 相乘的段都会把整个乘积拉成 0。所以遇到至多这种表述最后答案要在一个维度上再扫一遍取最大值。这个改动只有几行但如果不注意题目到底是恰好还是至多就会直接 WA。6.2 要求输出切分方案加一个决策点数组有些变体会要求你不只输出最大乘积还要输出具体的切分方式比如在第几位后面插乘号。这时候只需要在原来的转移里多记一个数组pre[i][j]表示计算dp[i][j]时选中的那个最优 t 是多少。转移的时候只要发现当前候选值比dp[i][j]大就顺手把pre[i][j] t记下来。最后从pre[n][K]出发往前回溯记t pre[n][K]那么最后一个乘号插在第 t 位后面接着跳到状态dp[t][K-1]取pre[t][K-1]以此类推直到乘号用完。回溯出来的位置序列反过来输出就是完整的切分方案。这个技巧的通用性极强几乎所有输出方案的 DP 题都是这个套路多开一个数组记录我是从哪个状态转移过来的。6.3 和石子合并矩阵连乘的家族关系如果你做过经典的石子合并或者矩阵连乘应该会有种熟悉感。那类题的状态是f[i][j]表示把第 i 堆到第 j 堆合并成一堆的最小代价枚举的是最后一次合并的分界点 k转移形如f[i][j] min(f[i][k] f[k1][j] 代价)。乘积最大这道题的结构其实是一样的枚举最后一段的起点只不过这道题的左半部分是从串首开始的前缀而不是任意区间。之所以有区别是因为石子合并要合并成一个整体所以左右两部分都是中间区间的形式而乘积最大的最终结果是一条从前到后的完整划分所以左边的状态天然就是前缀。理解了这个同构关系你会发现一大类题都能用同一套思考框架去套确定决策动作 → 确定状态维度 → 推出转移时枚举的分界点 → 确定边界和初始化 → 处理数值溢出和精度。这套流程走顺了区间 DP 这一类题基本就通了。我个人在实际刷题过程中的体会是像 1275 这种看起来简单的老题其实是最值得反复琢磨的。它把状态定义枚举边界高精度这三个动态规划的核心考点全揉在一起了每一处都能踩坑每一处也都能学到东西。第一次写不出来很正常把样例的那张 DP 表亲手推两遍再对着代码单步走一遍这道题就真正变成你自己的了。