看到“P1018 乘积最大高精度DP”这个题号大部分刷过算法题的朋友应该都不会陌生。这道题的核心场景很直白给你一串数字允许插入 K 个乘号求能得到的最大乘积。数字串长度从 6 到 40这个范围设计得非常巧妙——它能用 long long 接住的长度只有 20 位不到40 位数字一做乘法结果轻松冲破 64 位整数的天花板逼着你老老实实把高精度乘法自己实现一遍。整道题就是“动态规划做决策”和“高精度做计算”两个模块的组合拳备考信息学竞赛、练 DP 入门、或者想验证自己对字符串大数运算掌握程度的同学都值得拿它当试金石。我最初写这道题的时候第一反应是“这不就是个区间分割问题吗”结果被高精度部分的字符串下标、前导零、字符串比较坑到怀疑人生。这篇就把整个思路、代码、踩坑过程完整拆开照着走一遍你也能稳定 AC。1. 先搞清楚题目在考什么区间分割与最优子结构1.1 题目本质把数字串切成 K1 段N 位的数字串插入 K 个乘号之后整条串会被切成 K1 个连续的子段每一段都是原数字串的一个连续子串它自己作为整数参与乘法。我们要找的就是一组切割点让这些子串代表的整数的乘积最大。从组合数学角度看N-1 个空隙里选 K 个放乘号方案数是 C(N-1, K)。当 N40、K6 时这个数大约是 326 万理论上暴力枚举并不是完全不能跑。但注意枚举出方案之后还要做高精度乘法、比较大小而且 N 再大一点组合数会爆炸式增长所以暴力不可取。关键是这个问题的结构乘法天然具有“前缀最优”性质。如果我确定了最后一个乘号放在第 j 位和第 j1 位之间那么最后一个乘号左边的部分就变成了一个规模更小的同类问题——在前 j 位数字里插入 K-1 个乘号让左边部分乘积最大。左右两边互不影响子问题和原问题结构完全一致。这种最优子结构是动态规划能够生效的根本前提。1.2 DP 状态与转移为什么 dp[i][k] 这样定义状态设计是这个题的灵魂。我用 dp[i][k] 表示数字串前 i 位数字中放入 k 个乘号能得到的所有乘积中的最大值。为什么这样定义因为当我在考虑最后一个乘号放在哪里时只需要知道两件事最后一个乘号左侧一共处理了多少位、左侧一共用了多少个乘号。左侧部分的最优值就是 dp[j][k-1]右侧则是原数字串第 j1 到第 i 位形成的整数 num(j1, i)。转移方程很简洁dp[i][k] max( dp[j][k-1] * num(j1, i) )其中 j 从 k 枚举到 i-1。这里 j 的下界为什么是 k因为前 j 位里要放下 k-1 个乘号至少要 k 个数字字符所以 j k否则 dp[j][k-1] 根本不存在。j 的上界为什么是 i-1因为最后一个乘号右侧至少要留一位数字所以 j 最大只能到 i-1。初始状态是 dp[i][0] num(1, i)也就是一个乘号都不放的时候前 i 位直接作为一个整数。最终答案就是 dp[N][K]。我第一次做这题时把 i 理解成“数字串的下标”结果转移时切子串总差一位。后来在草稿纸上画了一行数字位标上 1 到 N 的下标再对照转移方程写代码一下就顺了。记住这里 i 代表“前 i 位”而不是“第 i 个字符”。1.3 边界条件与枚举范围一上来就写对的诀窍写三重循环时最容易出错的就是边界。把伪代码列出来for i 1; i N; i: dp[i][0] num(1, i)for k 1; k K; k: for i k 1; i N; i: for j k; j i; j: dp[i][k] max(dp[i][k], dp[j][k-1] * num(j1, i))第二层 i 要从 k1 开始因为前 i 位里放 k 个乘号至少要 k1 个数字字符。第三层 j 从 k 开始原因上面刚说过。这三个边界只要写对DP 部分就立住了。这个题的 DP 部分本质上和“矩阵连乘”“石子合并”这类区间 DP 是同一套思路枚举最后一步的分割点把问题拆成两个独立子问题。理解了这个你就掌握了这类题的通解模板。2. 高精度乘法40 位数字之下 long long 真的不够用2.1 数据范围推导乘积最多能达到多少位很多人第一反应是数字串最长 40 位用 long long 或者 __int128 不就行了我们来认真算一笔账。long long 最大约 9.22e18也就是 19 位十进制数。数字串本身 40 位随便切成两个 20 位左右的子段相乘结果就有 40 位超出 long long。再极端一点如果切成多个长度接近的段乘积位数会更夸张。比如把 40 位数字切成 6 段每段 6-7 位乘积结果大约在 40 位到 42 位之间如果某些段更长乘积位数可以逼近 60-80 位。__int128 最大约 1.7e38也就是 39 位十进制数同样扛不住。更别提有些评测环境对 __int128 支持不友好。所以这道题的高精度不是可有可无的工具而是题目本身就在考察的内容。你需要的不是完整的大数模板而是一个最小可用的高精度模块——只需要支持两个操作两个大数相乘、两个大数比较大小。乘法和比较是转移方程唯一的两种运算不需要加法、减法、除法比完整大数库简单太多了。2.2 高精度乘法的实现细节竖式模拟与进位处理高精度乘法的本质就是模拟小学竖式。用字符串表示数字例如123表示整数 123。乘法时让第一个数的每一位去乘第二个数的每一位把结果累加到对应位置。具体步骤开辟一个临时数组 tmp长度设为 len(a) len(b)因为两个长度分别为 la、lb 的数相乘乘积最多 lalb 位。从低位到高位遍历 a 的每一位再从低位到高位遍历 b 的每一位把 a[i] * b[j] 累加到 tmp[ij] 位置。所有累加完成后从低位到高位统一处理进位tmp[t1] tmp[t] / 10tmp[t] % 10。去掉前导零反转成高位在前的字符串返回。有一个特别容易翻车的地方字符串123里下标 0 是最高位下标 2 是个位。如果你直接拿两个原字符串从右往左乘下标的对应关系非常容易乱。最稳的写法是先把字符串反转让下标 0 对应个位循环写起来逻辑清晰最后再反转回高位在前。进位处理还有第二个坑乘法过程中某些位置累加出来的临时值可能远超 10比如 999 * 999中间位置可能累加到几十甚至上百。如果只在两层循环内部顺手进位很容易漏掉向更高位的连续进位。正确做法是先累加到临时数组两层循环结束后统一从左到右处理进位这样逻辑最干净。2.3 高精度比较大小长度优先字典序兜底比较两个大数字符串第一件事是确保字符串没有前导零构造时就处理掉。然后长度不同长度更长的一定更大。长度相同直接按字典序比较。因为两个同为长度 L 的字符串字典序比较本质上就是从最高位开始逐位比较高位大的数一定更大。这个逻辑简单但很多人会偷懒直接写if (a b)去比较字符串。对长度相同的数字串这个写法碰巧正确一旦长度不同比如999和1000字典序比较会得到1000 999 的错误结论。这道题里两个待比较的数可能位数差很大这个坑几乎是必踩的。我建议把高精度乘法单独写一个小测试输入两个最长 40 位的字符串用 Python 验证乘法结果是否一致。高精度部分确认无误之后DP 逻辑里的 bug 才能被准确暴露出来调试效率会高很多。3. 完整实现C 与 Python 双版本可复现代码3.1 C 版本从输入解析到输出结果整理一下整体流程。先把数字串按 1-based 下标切好所有子串存到 num[i][j] 里再初始化 dp[i][0]接着三重循环跑 DP最后输出 dp[N][K]。下面给一个可以直接跑的 C 实现关键边界和容易错的点我都标在注释里#include bits/stdc.h using namespace std; int N, K; string s; string num[45][45]; string dp[45][8]; // 高精度乘法返回字符串形式的结果 string mul(const string a, const string b) { if (a 0 || b 0) return 0; int la a.size(), lb b.size(); vectorint tmp(la lb, 0); // 从低位往高位乘先把字符串反转让下标0对应个位 for (int i 0; i la; i) { int ai a[la - 1 - i] - 0; for (int j 0; j lb; j) { int bj b[lb - 1 - j] - 0; tmp[i j] ai * bj; } } // 统一处理进位 for (int t 0; t la lb - 1; t) { tmp[t 1] tmp[t] / 10; tmp[t] % 10; } // 去掉前导零并翻转回高位在前 int pos la lb - 1; while (pos 0 tmp[pos] 0) pos--; string res; for (int t pos; t 0; t--) { res.push_back(char(0 tmp[t])); } return res; } // 高精度比较先比长度再比字典序 string bigmax(const string a, const string b) { if (a.size() ! b.size()) return a.size() b.size() ? a : b; return a b ? a : b; } int main() { cin N K; cin s; // 预处理所有子串num[i][j] 表示 s 从 i 到 j 的子串1-based for (int i 1; i N; i) for (int j i; j N; j) num[i][j] s.substr(i - 1, j - i 1); // 初始化一个乘号都不放 for (int i 1; i N; i) dp[i][0] num[1][i]; // DP 主体 for (int k 1; k K; k) { for (int i k 1; i N; i) { for (int j k; j i; j) { string cand mul(dp[j][k - 1], num[j 1][i]); dp[i][k] bigmax(dp[i][k], cand); } } } cout dp[N][K] endl; return 0; }这里 dp 数组第二维开到 8因为 K 最大是 6留一点余量。num 数组开到 45覆盖 N 最大 40。子串预处理一次性完成代价 O(N^2)对这个数据范围完全可接受。注意一个细节使用 bigmax 函数时dp[i][k] 必须预先有一个初值。上面代码里 dp 是 string 类型默认初值是空串空串参与 bigmax 会出错。所以要么把所有 dp[i][k] 初始化为0要么像这段代码一样在进入 k 循环前先将 dp[i][k] 设为0。我习惯在初始化阶段就把 dp[i][k] 全部赋成0这样 bigmax 永远不会遇到空串。3.2 Python 版本用内建大整数快速验证思路如果你刷题环境允许用 Python高精度部分可以直接省掉——Python 的整数是不限长度的。这对“验证 DP 思路是否写对”特别有帮助。我调 C 版本时就是这么干的先用 Python 跑一遍小数据拿到期望结果再回头对照 C 输出。# 输入格式第一行 N K第二行数字串 N, K map(int, input().strip().split()) s input().strip() dp [[0] * (K 1) for _ in range(N 1)] for i in range(1, N 1): dp[i][0] int(s[:i]) for k in range(1, K 1): for i in range(k 1, N 1): for j in range(k, i): left dp[j][k - 1] right int(s[j:i]) dp[i][k] max(dp[i][k], left * right) print(dp[N][K])这个版本里s[:i]表示前 i 位s[j:i]表示从第 j 位到第 i-1 位Python 切片左闭右开正好对应 C 里的 num[1][i] 和 num[j1][i]。int转换会自动处理前导零。这个版本和 C 版本一一对应非常适合用来对拍验证。3.3 代码里最容易被忽略的三个细节第一个细节是输入格式。数字串与 N、K 可能不在同一行数字串本身可能带换行。用cin s或者input().strip()都能处理换行和空格但如果你用getline去读数字串读完 N K 之后第一个读到的往往是残留的空行直接导致空串输入。这种问题本地一跑可能发现不了上评测机才暴露就很冤。第二个细节是 dp[i][0] 的初始化。直接把前 i 位转成数字字符串而不是先转成 int 再存。因为 N40 时前 i 位完全可能超过 int 范围一转换就溢出了。C 里直接用 num[1][i] 是最安全的。第三个细节是 dp 数组的初值。string 默认是空串空串参与比较会出问题。要么统一初始化成0要么在转移时先判空。我在两种写法上都踩过坑初始化成0后如果某个候选值真的是0bigmax 能正确处理但如果不初始化直接调用 bigmax(dp[i][k], cand)空串会被当成比0还小导致本该更新的值没更新。建议一开始就统一初始化不要混用。4. 手工推演样例把 DP 表一步步填出来4.1 用“1231”验证转移方程的正确性光看懂方程还不够我建议所有人都拿一个小样例在纸上推演一遍。比如数字串1231N4K2。直观来看要插两个乘号其实就是选两个位置把数字切成三段。所有切法如下1 * 2 * 31 621 * 23 * 1 2312 * 3 * 1 36最大的是 62答案取 62。现在用 DP 推演一遍。初始状态dp[1][0] 1 dp[2][0] 12 dp[3][0] 123 dp[4][0] 1231k1也就是放一个乘号dp[2][1] dp[1][0] * num[2][2] 1 * 2 2 dp[3][1] max(dp[1][0] * num[2][3] 23, dp[2][0] * num[3][3] 36) 36 dp[4][1] max(1231231, 1231372, 123*1123) 372这里 dp[4][1]372表示前 4 位放一个乘号时最大分割是 12*31。k2dp[3][2] dp[2][1] * num[3][3] 2 * 3 6 dp[4][2] max(dp[2][1] * num[3][4] 62, dp[3][1] * num[4][4] 36) 62最终答案 dp[4][2]62和暴力枚举一致。整个过程没有用到任何超过常规范围的运算但完整验证了状态定义、最后一步的分割点、子问题独立性这三个关键要素。我建议拿这个例子去对照代码调试把每一层循环的 cand 打印出来。如果第一遍跑出来不是 62问题大概率出在子串端点或者 j 的枚举范围上。4.2 边界问题自查清单除了样例再准备一组边界数据跑一遍心里才有底K1 的极端情况。比如数字串100000只插一个乘号切法包括 1000000、1000000 等等结果全是 0。这验证了高精度对零的处理乘法结果如果是 0字符串必须是0而不是空串。KN-1也就是乘号数量最多的情况。比如数字串2222K3结果是 222*216。此时转移里 j 最小是 kN-1iN正好只有一种切法。如果循环边界写错这里会直接访问非法状态。40 个 9 组成的大数K6。乘积很长正好用来验证高精度乘法的进位处理是否正确。把这些 case 全部跑一遍DP 和高精度基本就都稳了。5. 我在调试中遇到过的坑与排查心得5.1 字符串下标差一错误枚举区间时最容易翻车第一次写这题时我的 num 数组定义成 num[i][j] 表示第 i 位到第 j 位转移时写 j 从 k 开始、i 从 k1 开始结果样例输出跑出来是 36 而不是 62。当时打印了所有候选值发现计算 dp[4][2] 时右侧子串取成了 num[j][i] 而不是 num[j1][i]相当于把第 j 位字符重复算了一次。这类下标错误极其隐蔽小样例可能恰好答案不受影响换一组数据才会暴露。排查经验是在关键转移位置加调试输出打印 i、j、dp[j][k-1] 和右侧子串。把这些中间量列出来对照手工推演表一比对就能准确定位是哪一层循环的问题。不要靠眼睛盯着代码干猜我在这上面浪费过至少半小时。5.2 前导零、空串与比较函数的隐藏 bug高精度乘法返回结果前如果忘记去掉前导零会得到0123这样的字符串。表面看起来不影响数值但会影响字符串比较如果比较函数只用字典序0123和123长度不同字典序比较结果是0123 123导致该更新 dp 值时没更新。这个问题在乘积结果包含大量 0 时特别容易出现。另外乘法结果真的为零时比如某段子串是0000int 转换后是 0但字符串表达可能会变成空串。空串一旦进入转移比较函数就把空串当成最小乘积为 0 这个真实候选就丢了。所以我实现 mul 时开头会做一次判断如果任一操作数是0直接返回0。下面是我踩过坑之后整理的排查对照表写代码前对照一遍能少走很多弯路症状根本原因排查方法样例输出 36 而不是 62子串端点取错右侧子串多算一位或漏掉一位打印 i、j、left、right对照手工推演答案少很多位或出现0123乘法未去前导零检查 mul 返回前去零逻辑乘积为 0 时输出空行零子串返回了空串在 mul 开头判断全零并返回0比较结果异常比较函数直接用字符串字典序先比长度再比字典序5.3 性能与内存这个题到底需不需要优化N 最大 40K 最大 6三重循环里套的是字符串乘法复杂度乍一看是 O(N^2 * K * L^2)L 是数字串长度。实际算一下L^2 上限 1600N^21600K6乘起来大概千万级别C 几毫秒就能跑完。Python 因为有内建大整数速度也完全够。所以这个题不需要状态压缩、不需要滚动数组、不需要预处理高精度乘法表。唯一值得做的小优化是把子串预处理成 num 数组避免每次转移都调用 substr 截取。预处理完之后num[j1][i] 的访问是 O(1) 的代码也更清晰。如果连 num 数组都不想开直接用 s.substr(j, i-j) 临时截取也行数据小所以无所谓只是看起来没那么整洁。关于空间dp 数组是 41*7 的字符串数组每个字符串最多几十个字符内存占用可以忽略。完全没有必要把 dp 改成滚动数组第二维 k 只有 1 到 K滚动数组反而增加理解成本。在这个数据范围下优先保证正确性和可读性才是正经事。5.4 如果题目改一改这套解法还能怎么迁移做完这道题以后很多变体其实都在同一套框架里如果允许插入乘号和加号K 个符号可自由选择状态要增加一维表示当前符号类型本质上还是区间 DP 枚举最后符号。如果乘号数量不固定要求乘积最大且可以不放乘号那就是对所有 k 取 max(dp[N][k])。如果需要输出分割方案而不是最大乘积可以在每次更新 dp[i][k] 时记录对应的分割点 j最后回溯输出。N 很小这种方案记录完全可行。如果数字串允许前导零比如00123题目会变成另一种情况。本题原题保证数字串本身没有前导零这也是子串可以直接用字符串比较的原因之一。我个人把“乘积最大”当作一个练习模块来对待DP 部分学状态设计高精度部分学字符串运算合起来学的是“如何把两个基础模块组合成一个完整解法”。很多看起来吓人的题目拆开就是两个你本来就会的考点。先手工推演、再用 Python 对拍、最后用 C 提交——这个流程我后来一直在用稳定且不容易出错。