1. 项目概述从一道经典面试题说起最近在带新人刷题和准备面试时又遇到了“插入乘号”这道题。题目本身不复杂给定一个数字字符串比如“123”再给定一个整数k比如1要求你在数字串中插入k个乘号将字符串分成k1个部分使得这k1个数的乘积最大。对于“123”和k1显然插入在“12”和“3”之间得到12*336是最大乘积。这道题频繁出现在各大厂的笔试和面试中因为它完美地融合了字符串处理、区间划分和最优化思想是考察动态规划基本功的绝佳材料。很多朋友第一次接触时可能会尝试暴力枚举所有插入位置但字符串一长就立刻超时。这正是动态规划DP大显身手的地方。今天我就结合自己多年刷题和面试官的经验用C带你从暴力思路一步步优化到标准的区间DP解法并拆解其中所有容易踩坑的细节。无论你是正在备战面试还是想巩固DP思想这篇都能让你彻底搞懂这类“分割字符串求极值”问题的通用解法。2. 问题深入分析与暴力解法2.1 问题形式化定义与理解我们先抛开代码把问题彻底讲清楚。假设我们有一个数字字符串num其长度为n以及一个非负整数kk n。我们需要在这个字符串的n-1个空隙即相邻数字之间中选择恰好k个位置插入乘号。插入后原字符串被分割成k1个非空的数字子串。每个子串可以看作一个整数允许前导零但通常我们将其解析为整数数值。我们的目标是使这k1个整数的乘积最大化。举个例子num 105, k 1。我们有2个空隙可选在“1”和“05”之间或在“10”和“5”之间。方案A插入在1后:1 * 05 1 * 5 5方案B插入在10后:10 * 5 50显然最大乘积是50。这里注意“05”被解析为整数5。为什么这个问题有挑战性核心在于“选择”和“组合”。从n-1个空隙中选k个这是一个组合问题方案总数是 C(n-1, k)。当n和k稍大时比如n20k10组合数会变得非常庞大暴力枚举所有组合即递归尝试在每个空隙插入或不插入乘号的时间复杂度是指数级的完全不可接受。这就需要我们寻找更优的算法利用子问题的重叠性——这正是动态规划的用武之地。2.2 从暴力递归到DP的思维过渡在深入DP之前理解暴力递归有助于我们把握问题结构。一个最直观的暴力递归思路是定义一个递归函数dfs(start, remain_k)表示从字符串start位置开始还需要插入remain_k个乘号能获得的最大乘积。基准情况如果remain_k 0意味着从start到字符串末尾的这一整段就是一个数字我们直接返回其数值。递归情况我们需要决定第一个乘号插在哪里。我们可以在位置istart i n-1后面插入第一个乘号。这样我们得到了从start到i的子串构成的数字乘以递归调用dfs(i1, remain_k-1)的结果。我们遍历所有可能的i取乘积的最大值。这种递归树会大量重复计算相同的子问题例如不同的分割路径可能在后续到达相同的(start, remain_k)状态。动态规划的本质就是用一张表通常是二维数组把这些子问题的解存起来避免重复计算。我们定义dp[i][j]表示考虑字符串前i个字符即下标0到i-1插入j个乘号能获得的最大乘积。这里i从1计数到nj从0计数到k。最终答案就是dp[n][k]。注意这里有一个关键点dp[i][j]中的i是“长度”而不是“下标”。这是区间DP中处理子串的常见技巧可以避免下标计算的混乱。dp[i][j]对应的是子串num[0...i-1]。3. 动态规划状态设计与递推3.1 状态定义与初始化我们正式定义二维DP数组dp。dp[i][j]将字符串的前i个字符即num[0...i-1]分割成j1段即插入j个乘号所能获得的最大乘积。i的取值范围1 i n长度。j的取值范围0 j min(k, i-1)。因为要把长度为i的串分成j1段每段至少一个字符所以最多只能插入i-1个乘号。初始化当j 0时意味着不插入任何乘号整个前i个字符作为一个整体。因此dp[i][0]就应该等于这个整体数字的值。即dp[i][0] stoll(num.substr(0, i))。这里使用stollstring to long long是为了防止大数溢出虽然本题通常限制在可处理范围内但养成好习惯很重要。其他状态初始值可以设为0如果所有数字非负或一个非常小的数如果考虑负数本题通常不考虑因为我们要取最大值。3.2 状态转移方程推导这是整个算法的核心。如何计算dp[i][j](j 1)我们可以这样思考为了将前i个字符分成j1段我们可以先确定最后一段的起始位置。假设最后一段是从第m个字符开始1-indexed到第i个字符结束。那么前面m-1个字符即num[0...m-2]就需要被分成j段因为我们已经用掉了最后一个乘号来分隔最后一段。最后一段的数字值我们记为last_num它等于num[m-1...i-1]转换成的整数。因此dp[i][j]应该等于所有可能的m取值下dp[m-1][j-1] * last_num的最大值。m的取值范围是多少因为最后一段至少需要1个字符所以m至少为j前面m-1个字符要分成j段每段至少1字符所以 m-1 j m j1。同时m不能超过i最后一段至少1字符所以 m i。更精确地说j m-1且m i。所以转移方程为dp[i][j] max( dp[m-1][j-1] * num_val(m, i) )其中j m-1 inum_val(m, i)表示子串num[m-1...i-1]的整数值。为什么这样是对的这体现了动态规划的“最优子结构”性质为了得到前i个字符插入j个乘号的最优解我们枚举最后一个乘号的位置。在最优解中最后一个乘号左边的部分前m-1个字符插入j-1个乘号也必然是其自身子问题的最优解即dp[m-1][j-1]。如果不是我们可以用更优的方案替换它从而得到整个问题更优的解这就矛盾了。3.3 预计算数字值优化在状态转移中我们需要频繁计算任意子串num[l...r]对应的整数值。如果在每次转移时都临时用stoll或循环计算会带来 O(n) 的额外开销使得总复杂度达到 O(n^3 * k)这在 n 较大时可能不够高效。一个经典的优化是预计算一个二维数组numVal[l][r]表示子串num[l...r]l, r 为0-indexed下标的整数值。计算方式可以通过动态规划numVal[i][i] num[i] - 0。numVal[i][j] numVal[i][j-1] * 10 (num[j] - 0)。 (i j) 这样我们可以在 O(n^2) 时间内预处理所有子串的数值之后在DP转移中需要num_val(m, i)时直接查表numVal[m-1][i-1]即可时间复杂度 O(1)。实操心得对于字符串长度 n 达到几十甚至上百的题目这个预处理至关重要。即使 n 较小这也是一种良好的编程习惯让主DP逻辑更清晰避免在循环中重复进行字符串截取和转换。4. C实现与代码逐行解析接下来我们结合上述分析给出完整的C实现。我会在关键代码处添加详细注释。#include iostream #include vector #include string #include algorithm #include climits using namespace std; long long maxProductAfterInsertion(const string num, int k) { int n num.size(); if (n 0 || k n) return 0; // 边界情况处理 // 1. 预计算所有子串的数值 vectorvectorlong long numVal(n, vectorlong long(n, 0)); for (int i 0; i n; i) { long long cur 0; for (int j i; j n; j) { cur cur * 10 (num[j] - 0); numVal[i][j] cur; } } // 2. DP数组初始化dp[i][j] 前i个字符长度插入j个乘号 // i: 1~n, j: 0~k vectorvectorlong long dp(n 1, vectorlong long(k 1, 0)); // 初始化 j0 的情况即不插入乘号 for (int i 1; i n; i) { dp[i][0] numVal[0][i - 1]; // 子串[0, i-1]的值 } // 3. 状态转移 for (int i 1; i n; i) { // 考虑前i个字符 for (int j 1; j min(k, i - 1); j) { // 插入乘号数不能超过i-1 long long maxProd 0; // 枚举最后一个乘号的位置它使得最后一段从第m个字符开始 // 前面有 m-1 个字符需要插入 j-1 个乘号 // m 至少为 j因为前面m-1 j-1 m j且 m i for (int m j; m i; m) { // 注意m是长度对应最后一段起点下标m-1 // 前 m-1 个字符插入 j-1 个乘号的最大乘积 long long prev dp[m - 1][j - 1]; // 最后一段子串为 num[m-1 ... i-1] long long lastNum numVal[m - 1][i - 1]; long long curProd prev * lastNum; if (curProd maxProd) { maxProd curProd; } } dp[i][j] maxProd; } } // 4. 返回结果 return dp[n][k]; } int main() { string num; int k; cout 请输入数字字符串: ; cin num; cout 请输入要插入的乘号数量k: ; cin k; long long result maxProductAfterInsertion(num, k); cout 插入 k 个乘号后最大乘积为: result endl; return 0; }代码关键点解析numVal数组numVal[i][j]存储的是子串num[i...j]的数值。计算方式采用了递推避免了每次重复计算。DP数组维度dp数组大小为(n1) x (k1)dp[i][j]中的i代表“前i个字符”长度。这种以长度为索引的方式在处理子串问题时非常常见能减少边界错误。循环范围外层i循环从1到n代表当前处理的字符串总长度。中层j循环从1到min(k, i-1)。j不能大于k同时要把长度为i的串分成j1段必须满足i j1即j i-1。内层m循环枚举最后一个乘号“之前”的字符数m-1。因为前面部分需要分成j段插入j-1个乘号所以前面至少要有j个字符每段至少一个即m-1 j-1m j。同时最后一段至少一个字符所以m i。乘积计算curProd dp[m-1][j-1] * numVal[m-1][i-1]。这里dp[m-1][j-1]是子问题最优解numVal[m-1][i-1]是最后一段的数值。返回值dp[n][k]即为所求。复杂度分析时间复杂度预处理numVal需要 O(n^2)。DP过程有三重循环复杂度为 O(n^2 * k)。因为内层m循环平均长度是 O(n)所以总复杂度可视为 O(n^3) 级别当k接近n时。对于常规面试题n 50, k 10完全可接受。空间复杂度O(n^2) 用于存储numVal和dp。5. 边界条件、陷阱与实战调试5.1 必须处理的边界情况空字符串或k值过大如果输入字符串为空或者k n那么无法形成k1个非空子串问题无解。通常题目会保证0 k n但防御性编程要考虑。代码开头已处理。大数溢出乘积可能非常大。即使使用long long通常64位最大值约9e18当数字串较长且分割段数多时仍可能溢出。在面试中需要主动询问数据范围。如果可能溢出可能需要使用高精度计算如用字符串模拟大数乘法但这会大大增加编码复杂度。通常笔试/面试会保证结果在long long范围内。前导零的处理我们的算法将子串直接转换为整数前导零会被自动忽略如“05”变成5。这符合题目的一般要求。但务必在解题开始时向面试官确认这一点。初始化dp[i][0]一定要正确初始化。dp[i][0]必须等于整个前i位字符串的值而不是0或1。5.2 一个完整的调试案例让我们以num 312, k 1为例手动过一遍算法加深理解。预处理numValnumVal[0][0]3,[0][1]31,[0][2]312numVal[1][1]1,[1][2]12numVal[2][2]2初始化dp[i][0]dp[1][0] numVal[0][0] 3dp[2][0] numVal[0][1] 31dp[3][0] numVal[0][2] 312状态转移计算dp[2][1](i2, j1)m 从 j1 到 i2。m1:dp[0][0] * numVal[0][1]。dp[0][0]需要定义通常表示空串乘积为1这里更合理的定义是当 m1 时前面有0个字符插入 j-10 个乘号这应该是一种边界。我们可以定义dp[0][0] 1乘法的单位元而其他dp[0][j](j0) 无效设为0。所以1 * 31 31。m2:dp[1][0] * numVal[1][1] 3 * 1 3。最大值是31。所以dp[2][1] 31。这对应将“31”分成两段的最大乘积不对i2是前两个字符“31”插入1个乘号只能在中间插得到3*13。我们算出来31这里出错了发现bug我们的状态定义dp[i][j]是前i个字符插入j个乘号。对于“31”(i2)插入1个乘号只能分成“3”和“1”乘积是3。但我们计算中m1的情况对应dp[0][0] * numVal[0][1]这意味着前面0个字符空串作为一段后面“31”作为一段这实际上只形成了1段而不是j12段。这违反了“分成j1段”的约束。问题出在m的枚举起点上。修正最后一个乘号的位置m表示最后一段的起点。前面需要有m-1个字符。为了将这m-1个字符分成j段即插入j-1个乘号必须满足m-1 j-1即m j。同时最后一段至少1个字符所以m i。这看起来没错。但关键在于dp[m-1][j-1]必须有效即m-1 1不对dp[0][0]应该有效它表示空串分成0段不插入乘号的“乘积”这个值定义为1是合理的用于乘法。但是dp[0][0]代表空串它不能作为“一段”参与乘积吗在我们的分割中每一段都必须对应原串的非空子串。如果m1意味着前面是空串这不是一个有效的段。因此m必须至少为j1以确保前面有至少j个字符才能分成j段每段至少一个字符。更准确的条件是m-1 jm j1。让我们修正内层循环的m范围for (int m j1; m i; m)。重新计算dp[2][1]m 从 2 到 2。m2:dp[1][0] * numVal[1][1] 3 * 1 3。正确。再计算dp[3][1](i3, j1)m 从 2 到 3。m2:dp[1][0] * numVal[1][2] 3 * 12 36。m3:dp[2][0] * numVal[2][2] 31 * 2 62。最大值62对应分割“31”和“2”即31*262。正确。再验证一个dp[3][2](i3, j2)m 从 3 到 3 (因为 j13)。m3:dp[2][1] * numVal[2][2] 3 * 2 6。这对应将“312”分成3段方案是“3”、“1”、“2”乘积为6。正确。所以正确的内层循环起始条件是m j1。这是本题实现中非常容易出错的一个点它确保了在状态转移时前后两部分都是非空的子串。修正后的代码片段如下for (int i 1; i n; i) { for (int j 1; j min(k, i - 1); j) { long long maxProd 0; // 枚举最后一段的起点长度m。前面长度为 m-1需分成j段 m-1 j m j1 for (int m j 1; m i; m) { long long prev dp[m - 1][j - 1]; long long lastNum numVal[m - 1][i - 1]; long long curProd prev * lastNum; if (curProd maxProd) { maxProd curProd; } } dp[i][j] maxProd; } }5.3 初始化dp[0][0]为了处理边界我们还需要定义dp[0][0] 1。这样当m j1且j1时dp[m-1][j-1]即dp[j][0]是有效的。在我们的循环中dp[1][0],dp[2][0]等都已正确初始化。dp[0][0]只在理论推导时用到确保乘法起点的正确性。可以在DP数组声明后直接设置dp[0][0] 1。6. 算法扩展与变种思考掌握了基础解法后我们来看看相关的变种和扩展这能帮助你在面试中应对自如。6.1 如果要求输出具体插入方案上述DP只给出了最大乘积的值。如果面试官要求输出一种能达到最大乘积的插入方案即乘号的位置我们需要在DP过程中记录“决策点”。我们可以用另一个二维数组cut[i][j]记录在状态dp[i][j]取得最大值时最后一个乘号之前有多少个字符即我们转移方程中的m-1。然后在DP结束后我们可以从cut[n][k]开始反向回溯复原出所有乘号的位置。代码修改思路在计算dp[i][j]的内层循环中当找到更大的curProd时不仅更新maxProd同时记录cut[i][j] m-1。复原时从in, jk开始。设pos cut[i][j]这意味着在子串num[0...i-1]的解决方案中最后一个乘号是插在第pos个字符之后0-indexed。然后我们递归处理前半部分num[0...pos-1]和j-1个乘号的问题。6.2 如果数字串包含负号或小数点原题通常是纯数字字符串。如果扩展为包含负号和小数点的数字字符串例如“12-3.5”问题会复杂很多。负号乘积的正负性会受到影响。DP状态可能需要同时记录最大正值和最小负值因为负数乘负数得正数。这类似于“最大子数组乘积”问题的思路。小数点子串解析不再是整数而是浮点数。这涉及精度问题可能要用double或高精度小数库。状态转移中的乘法也变成浮点乘法。 这类变种在面试中较少见但知道思路能体现你的知识迁移能力。6.3 与经典DP问题的联系“插入乘号”问题可以看作是“分割字符串”类DP的一个典型代表。它与以下问题同源矩阵链乘给定一系列矩阵决定乘法顺序使得标量乘法次数最少。两者都是通过枚举“最后一次操作”的位置进行状态转移。分割回文串给定字符串求最少分割次数使得每段都是回文串。状态定义和转移枚举分割点的方式非常相似。解码方法数字串解码成字母求解码方式总数。也是线性DP考虑当前位置与前一个位置的关系。识别出这类问题的共性——定义dp[i]为考虑前i个字符的最优解或方案数然后枚举最后一段的起点——是解决一大批字符串分割DP问题的钥匙。7. 性能优化与工程化考虑7.1 空间复杂度优化我们的DP使用了 O(n * k) 的空间。观察状态转移方程dp[i][j]只依赖于dp[0...i-1][j-1]即上一列j-1的数据。因此我们可以使用滚动数组将空间复杂度优化到 O(n)。具体做法是只维护两个一维数组prev和curr分别代表j-1列和j列。vectorlong long dp(n 1, 0); // 初始化 j0 列 for (int i 1; i n; i) { dp[i] numVal[0][i - 1]; } for (int j 1; j k; j) { vectorlong long new_dp(n 1, 0); // 注意i的起始至少需要 j1 个字符才能插入j个乘号 for (int i j 1; i n; i) { long long maxProd 0; for (int m j 1; m i; m) { long long curProd dp[m - 1] * numVal[m - 1][i - 1]; maxProd max(maxProd, curProd); } new_dp[i] maxProd; } dp move(new_dp); // 滚动到下一列 } return dp[n];注意在滚动数组实现中dp[i]在每一轮外循环固定j中代表的是“前i个字符插入当前考虑的乘号数量”的最大乘积。初始化dp为j0的情况。然后对于每个j我们计算新的new_dp计算完后将其赋给dp用于下一轮。同时i的循环可以从j1开始因为少于这个长度无法插入j个乘号。7.2 大数处理与高精度实现如果题目明确提示结果可能超过long long范围例如数字串长度上百就需要实现高精度乘法。我们可以用字符串或数组来表示大整数。dp数组和numVal数组都将存储大数对象。状态转移中的乘法变为高精度乘法。这会显著增加代码量但思路完全不变。在面试中除非特别说明否则通常不需要写高精度但可以口头讨论这种可能性。7.3 测试用例设计自己测试时要覆盖各种边界和特殊情况最小输入n1, k0。dp[1][0]应等于该数字本身。k0不插入任何乘号应返回整个字符串转换的数字。kn-1在每个空隙都插入乘号乘积等于各数字相乘。包含零的数字串如10203, k1。零会影响乘积需要算法正确处理。单调数字串如12345插入乘号时往往倾向于将大数尽量留在后面或前面可以手动验证。大数测试随机生成长度适中的数字串用暴力搜索小规模验证DP结果的正确性。8. 常见面试提问与回答思路如果你在面试中遇到这道题面试官可能会沿着以下路径追问Q: 请描述一下你的思路。A: 这是一个最优化问题暴力枚举所有插入位置组合不可行。我注意到问题具有最优子结构性质为了求前i个字符插入j个乘号的最大乘积可以枚举最后一个乘号的位置。假设最后一个乘号放在第m个字符后那么问题分解为求前m个字符插入j-1个乘号的最大乘积乘以最后一段字符代表的数字。这自然引导我用动态规划定义dp[i][j]用三重循环实现。Q: 时间复杂度是多少能优化吗A: 预处理子串数值O(n^2)DP过程三重循环O(n^2 * k)。在k接近n时是O(n^3)。对于给定的约束通常n50是可以接受的。空间复杂度O(n^2)可以优化到O(n)使用滚动数组。进一步的优化可能涉及利用数学性质比如对于正数乘积最大往往希望各部分尽可能均匀类似算术-几何平均不等式但字符串分割是离散的这个性质不能直接用来剪枝所以O(n^3)可能已是较优解。Q: 如果数字串很长比如n1000你的算法会有什么问题A: 主要问题是时间复杂度O(n^3)会达到10^9级别不可接受。空间复杂度O(n^2)也需要10^6的存储可能可以承受但效率低。对于更大的n可能需要更高效的算法或者题目会限制k很小比如k10这样复杂度是O(n^2 * k)或许可行。另一个问题是乘积可能极大需要高精度计算这又会增加常数时间。Q: 如何修改代码以输出插入乘号的具体位置A: 可以在DP过程中维护一个平行的数组cut[i][j]记录状态dp[i][j]取得最大值时最后一个乘号左边子串的长度或最后一个乘号的位置。DP结束后从cut[n][k]开始回溯递归地找到所有乘号的位置。Q: 这和矩阵链乘问题有什么相似之处A: 两者都是通过“枚举最后一次操作的位置”来划分问题。矩阵链乘是选择最后一次乘法的位置将矩阵链分成左右两部分分别计算左右部分的最少乘法次数然后加上合并的代价。插入乘号是枚举最后一个乘号的位置将字符串分成左右两部分分别计算左部分插入一定数量乘号的最大乘积然后乘以右部分的数值。状态转移方程的结构非常相似都是区间DP的经典形式。这道“插入乘号”的题目虽然代码实现只有几十行但它涵盖了动态规划的核心状态定义、转移方程、边界处理、优化技巧。理解透彻这一道题就能触类旁通解决一大类字符串分割最优化问题。在实际编写时务必注意内层循环的起始条件m j1和dp[0][0]的初始化这是通过手动调试一个小案例才能深刻领会的细节。
1. 项目概述从一道经典面试题说起最近在带新人刷题和准备面试时又遇到了“插入乘号”这道题。题目本身不复杂给定一个数字字符串比如“123”再给定一个整数k比如1要求你在数字串中插入k个乘号将字符串分成k1个部分使得这k1个数的乘积最大。对于“123”和k1显然插入在“12”和“3”之间得到12*336是最大乘积。这道题频繁出现在各大厂的笔试和面试中因为它完美地融合了字符串处理、区间划分和最优化思想是考察动态规划基本功的绝佳材料。很多朋友第一次接触时可能会尝试暴力枚举所有插入位置但字符串一长就立刻超时。这正是动态规划DP大显身手的地方。今天我就结合自己多年刷题和面试官的经验用C带你从暴力思路一步步优化到标准的区间DP解法并拆解其中所有容易踩坑的细节。无论你是正在备战面试还是想巩固DP思想这篇都能让你彻底搞懂这类“分割字符串求极值”问题的通用解法。2. 问题深入分析与暴力解法2.1 问题形式化定义与理解我们先抛开代码把问题彻底讲清楚。假设我们有一个数字字符串num其长度为n以及一个非负整数kk n。我们需要在这个字符串的n-1个空隙即相邻数字之间中选择恰好k个位置插入乘号。插入后原字符串被分割成k1个非空的数字子串。每个子串可以看作一个整数允许前导零但通常我们将其解析为整数数值。我们的目标是使这k1个整数的乘积最大化。举个例子num 105, k 1。我们有2个空隙可选在“1”和“05”之间或在“10”和“5”之间。方案A插入在1后:1 * 05 1 * 5 5方案B插入在10后:10 * 5 50显然最大乘积是50。这里注意“05”被解析为整数5。为什么这个问题有挑战性核心在于“选择”和“组合”。从n-1个空隙中选k个这是一个组合问题方案总数是 C(n-1, k)。当n和k稍大时比如n20k10组合数会变得非常庞大暴力枚举所有组合即递归尝试在每个空隙插入或不插入乘号的时间复杂度是指数级的完全不可接受。这就需要我们寻找更优的算法利用子问题的重叠性——这正是动态规划的用武之地。2.2 从暴力递归到DP的思维过渡在深入DP之前理解暴力递归有助于我们把握问题结构。一个最直观的暴力递归思路是定义一个递归函数dfs(start, remain_k)表示从字符串start位置开始还需要插入remain_k个乘号能获得的最大乘积。基准情况如果remain_k 0意味着从start到字符串末尾的这一整段就是一个数字我们直接返回其数值。递归情况我们需要决定第一个乘号插在哪里。我们可以在位置istart i n-1后面插入第一个乘号。这样我们得到了从start到i的子串构成的数字乘以递归调用dfs(i1, remain_k-1)的结果。我们遍历所有可能的i取乘积的最大值。这种递归树会大量重复计算相同的子问题例如不同的分割路径可能在后续到达相同的(start, remain_k)状态。动态规划的本质就是用一张表通常是二维数组把这些子问题的解存起来避免重复计算。我们定义dp[i][j]表示考虑字符串前i个字符即下标0到i-1插入j个乘号能获得的最大乘积。这里i从1计数到nj从0计数到k。最终答案就是dp[n][k]。注意这里有一个关键点dp[i][j]中的i是“长度”而不是“下标”。这是区间DP中处理子串的常见技巧可以避免下标计算的混乱。dp[i][j]对应的是子串num[0...i-1]。3. 动态规划状态设计与递推3.1 状态定义与初始化我们正式定义二维DP数组dp。dp[i][j]将字符串的前i个字符即num[0...i-1]分割成j1段即插入j个乘号所能获得的最大乘积。i的取值范围1 i n长度。j的取值范围0 j min(k, i-1)。因为要把长度为i的串分成j1段每段至少一个字符所以最多只能插入i-1个乘号。初始化当j 0时意味着不插入任何乘号整个前i个字符作为一个整体。因此dp[i][0]就应该等于这个整体数字的值。即dp[i][0] stoll(num.substr(0, i))。这里使用stollstring to long long是为了防止大数溢出虽然本题通常限制在可处理范围内但养成好习惯很重要。其他状态初始值可以设为0如果所有数字非负或一个非常小的数如果考虑负数本题通常不考虑因为我们要取最大值。3.2 状态转移方程推导这是整个算法的核心。如何计算dp[i][j](j 1)我们可以这样思考为了将前i个字符分成j1段我们可以先确定最后一段的起始位置。假设最后一段是从第m个字符开始1-indexed到第i个字符结束。那么前面m-1个字符即num[0...m-2]就需要被分成j段因为我们已经用掉了最后一个乘号来分隔最后一段。最后一段的数字值我们记为last_num它等于num[m-1...i-1]转换成的整数。因此dp[i][j]应该等于所有可能的m取值下dp[m-1][j-1] * last_num的最大值。m的取值范围是多少因为最后一段至少需要1个字符所以m至少为j前面m-1个字符要分成j段每段至少1字符所以 m-1 j m j1。同时m不能超过i最后一段至少1字符所以 m i。更精确地说j m-1且m i。所以转移方程为dp[i][j] max( dp[m-1][j-1] * num_val(m, i) )其中j m-1 inum_val(m, i)表示子串num[m-1...i-1]的整数值。为什么这样是对的这体现了动态规划的“最优子结构”性质为了得到前i个字符插入j个乘号的最优解我们枚举最后一个乘号的位置。在最优解中最后一个乘号左边的部分前m-1个字符插入j-1个乘号也必然是其自身子问题的最优解即dp[m-1][j-1]。如果不是我们可以用更优的方案替换它从而得到整个问题更优的解这就矛盾了。3.3 预计算数字值优化在状态转移中我们需要频繁计算任意子串num[l...r]对应的整数值。如果在每次转移时都临时用stoll或循环计算会带来 O(n) 的额外开销使得总复杂度达到 O(n^3 * k)这在 n 较大时可能不够高效。一个经典的优化是预计算一个二维数组numVal[l][r]表示子串num[l...r]l, r 为0-indexed下标的整数值。计算方式可以通过动态规划numVal[i][i] num[i] - 0。numVal[i][j] numVal[i][j-1] * 10 (num[j] - 0)。 (i j) 这样我们可以在 O(n^2) 时间内预处理所有子串的数值之后在DP转移中需要num_val(m, i)时直接查表numVal[m-1][i-1]即可时间复杂度 O(1)。实操心得对于字符串长度 n 达到几十甚至上百的题目这个预处理至关重要。即使 n 较小这也是一种良好的编程习惯让主DP逻辑更清晰避免在循环中重复进行字符串截取和转换。4. C实现与代码逐行解析接下来我们结合上述分析给出完整的C实现。我会在关键代码处添加详细注释。#include iostream #include vector #include string #include algorithm #include climits using namespace std; long long maxProductAfterInsertion(const string num, int k) { int n num.size(); if (n 0 || k n) return 0; // 边界情况处理 // 1. 预计算所有子串的数值 vectorvectorlong long numVal(n, vectorlong long(n, 0)); for (int i 0; i n; i) { long long cur 0; for (int j i; j n; j) { cur cur * 10 (num[j] - 0); numVal[i][j] cur; } } // 2. DP数组初始化dp[i][j] 前i个字符长度插入j个乘号 // i: 1~n, j: 0~k vectorvectorlong long dp(n 1, vectorlong long(k 1, 0)); // 初始化 j0 的情况即不插入乘号 for (int i 1; i n; i) { dp[i][0] numVal[0][i - 1]; // 子串[0, i-1]的值 } // 3. 状态转移 for (int i 1; i n; i) { // 考虑前i个字符 for (int j 1; j min(k, i - 1); j) { // 插入乘号数不能超过i-1 long long maxProd 0; // 枚举最后一个乘号的位置它使得最后一段从第m个字符开始 // 前面有 m-1 个字符需要插入 j-1 个乘号 // m 至少为 j因为前面m-1 j-1 m j且 m i for (int m j; m i; m) { // 注意m是长度对应最后一段起点下标m-1 // 前 m-1 个字符插入 j-1 个乘号的最大乘积 long long prev dp[m - 1][j - 1]; // 最后一段子串为 num[m-1 ... i-1] long long lastNum numVal[m - 1][i - 1]; long long curProd prev * lastNum; if (curProd maxProd) { maxProd curProd; } } dp[i][j] maxProd; } } // 4. 返回结果 return dp[n][k]; } int main() { string num; int k; cout 请输入数字字符串: ; cin num; cout 请输入要插入的乘号数量k: ; cin k; long long result maxProductAfterInsertion(num, k); cout 插入 k 个乘号后最大乘积为: result endl; return 0; }代码关键点解析numVal数组numVal[i][j]存储的是子串num[i...j]的数值。计算方式采用了递推避免了每次重复计算。DP数组维度dp数组大小为(n1) x (k1)dp[i][j]中的i代表“前i个字符”长度。这种以长度为索引的方式在处理子串问题时非常常见能减少边界错误。循环范围外层i循环从1到n代表当前处理的字符串总长度。中层j循环从1到min(k, i-1)。j不能大于k同时要把长度为i的串分成j1段必须满足i j1即j i-1。内层m循环枚举最后一个乘号“之前”的字符数m-1。因为前面部分需要分成j段插入j-1个乘号所以前面至少要有j个字符每段至少一个即m-1 j-1m j。同时最后一段至少一个字符所以m i。乘积计算curProd dp[m-1][j-1] * numVal[m-1][i-1]。这里dp[m-1][j-1]是子问题最优解numVal[m-1][i-1]是最后一段的数值。返回值dp[n][k]即为所求。复杂度分析时间复杂度预处理numVal需要 O(n^2)。DP过程有三重循环复杂度为 O(n^2 * k)。因为内层m循环平均长度是 O(n)所以总复杂度可视为 O(n^3) 级别当k接近n时。对于常规面试题n 50, k 10完全可接受。空间复杂度O(n^2) 用于存储numVal和dp。5. 边界条件、陷阱与实战调试5.1 必须处理的边界情况空字符串或k值过大如果输入字符串为空或者k n那么无法形成k1个非空子串问题无解。通常题目会保证0 k n但防御性编程要考虑。代码开头已处理。大数溢出乘积可能非常大。即使使用long long通常64位最大值约9e18当数字串较长且分割段数多时仍可能溢出。在面试中需要主动询问数据范围。如果可能溢出可能需要使用高精度计算如用字符串模拟大数乘法但这会大大增加编码复杂度。通常笔试/面试会保证结果在long long范围内。前导零的处理我们的算法将子串直接转换为整数前导零会被自动忽略如“05”变成5。这符合题目的一般要求。但务必在解题开始时向面试官确认这一点。初始化dp[i][0]一定要正确初始化。dp[i][0]必须等于整个前i位字符串的值而不是0或1。5.2 一个完整的调试案例让我们以num 312, k 1为例手动过一遍算法加深理解。预处理numValnumVal[0][0]3,[0][1]31,[0][2]312numVal[1][1]1,[1][2]12numVal[2][2]2初始化dp[i][0]dp[1][0] numVal[0][0] 3dp[2][0] numVal[0][1] 31dp[3][0] numVal[0][2] 312状态转移计算dp[2][1](i2, j1)m 从 j1 到 i2。m1:dp[0][0] * numVal[0][1]。dp[0][0]需要定义通常表示空串乘积为1这里更合理的定义是当 m1 时前面有0个字符插入 j-10 个乘号这应该是一种边界。我们可以定义dp[0][0] 1乘法的单位元而其他dp[0][j](j0) 无效设为0。所以1 * 31 31。m2:dp[1][0] * numVal[1][1] 3 * 1 3。最大值是31。所以dp[2][1] 31。这对应将“31”分成两段的最大乘积不对i2是前两个字符“31”插入1个乘号只能在中间插得到3*13。我们算出来31这里出错了发现bug我们的状态定义dp[i][j]是前i个字符插入j个乘号。对于“31”(i2)插入1个乘号只能分成“3”和“1”乘积是3。但我们计算中m1的情况对应dp[0][0] * numVal[0][1]这意味着前面0个字符空串作为一段后面“31”作为一段这实际上只形成了1段而不是j12段。这违反了“分成j1段”的约束。问题出在m的枚举起点上。修正最后一个乘号的位置m表示最后一段的起点。前面需要有m-1个字符。为了将这m-1个字符分成j段即插入j-1个乘号必须满足m-1 j-1即m j。同时最后一段至少1个字符所以m i。这看起来没错。但关键在于dp[m-1][j-1]必须有效即m-1 1不对dp[0][0]应该有效它表示空串分成0段不插入乘号的“乘积”这个值定义为1是合理的用于乘法。但是dp[0][0]代表空串它不能作为“一段”参与乘积吗在我们的分割中每一段都必须对应原串的非空子串。如果m1意味着前面是空串这不是一个有效的段。因此m必须至少为j1以确保前面有至少j个字符才能分成j段每段至少一个字符。更准确的条件是m-1 jm j1。让我们修正内层循环的m范围for (int m j1; m i; m)。重新计算dp[2][1]m 从 2 到 2。m2:dp[1][0] * numVal[1][1] 3 * 1 3。正确。再计算dp[3][1](i3, j1)m 从 2 到 3。m2:dp[1][0] * numVal[1][2] 3 * 12 36。m3:dp[2][0] * numVal[2][2] 31 * 2 62。最大值62对应分割“31”和“2”即31*262。正确。再验证一个dp[3][2](i3, j2)m 从 3 到 3 (因为 j13)。m3:dp[2][1] * numVal[2][2] 3 * 2 6。这对应将“312”分成3段方案是“3”、“1”、“2”乘积为6。正确。所以正确的内层循环起始条件是m j1。这是本题实现中非常容易出错的一个点它确保了在状态转移时前后两部分都是非空的子串。修正后的代码片段如下for (int i 1; i n; i) { for (int j 1; j min(k, i - 1); j) { long long maxProd 0; // 枚举最后一段的起点长度m。前面长度为 m-1需分成j段 m-1 j m j1 for (int m j 1; m i; m) { long long prev dp[m - 1][j - 1]; long long lastNum numVal[m - 1][i - 1]; long long curProd prev * lastNum; if (curProd maxProd) { maxProd curProd; } } dp[i][j] maxProd; } }5.3 初始化dp[0][0]为了处理边界我们还需要定义dp[0][0] 1。这样当m j1且j1时dp[m-1][j-1]即dp[j][0]是有效的。在我们的循环中dp[1][0],dp[2][0]等都已正确初始化。dp[0][0]只在理论推导时用到确保乘法起点的正确性。可以在DP数组声明后直接设置dp[0][0] 1。6. 算法扩展与变种思考掌握了基础解法后我们来看看相关的变种和扩展这能帮助你在面试中应对自如。6.1 如果要求输出具体插入方案上述DP只给出了最大乘积的值。如果面试官要求输出一种能达到最大乘积的插入方案即乘号的位置我们需要在DP过程中记录“决策点”。我们可以用另一个二维数组cut[i][j]记录在状态dp[i][j]取得最大值时最后一个乘号之前有多少个字符即我们转移方程中的m-1。然后在DP结束后我们可以从cut[n][k]开始反向回溯复原出所有乘号的位置。代码修改思路在计算dp[i][j]的内层循环中当找到更大的curProd时不仅更新maxProd同时记录cut[i][j] m-1。复原时从in, jk开始。设pos cut[i][j]这意味着在子串num[0...i-1]的解决方案中最后一个乘号是插在第pos个字符之后0-indexed。然后我们递归处理前半部分num[0...pos-1]和j-1个乘号的问题。6.2 如果数字串包含负号或小数点原题通常是纯数字字符串。如果扩展为包含负号和小数点的数字字符串例如“12-3.5”问题会复杂很多。负号乘积的正负性会受到影响。DP状态可能需要同时记录最大正值和最小负值因为负数乘负数得正数。这类似于“最大子数组乘积”问题的思路。小数点子串解析不再是整数而是浮点数。这涉及精度问题可能要用double或高精度小数库。状态转移中的乘法也变成浮点乘法。 这类变种在面试中较少见但知道思路能体现你的知识迁移能力。6.3 与经典DP问题的联系“插入乘号”问题可以看作是“分割字符串”类DP的一个典型代表。它与以下问题同源矩阵链乘给定一系列矩阵决定乘法顺序使得标量乘法次数最少。两者都是通过枚举“最后一次操作”的位置进行状态转移。分割回文串给定字符串求最少分割次数使得每段都是回文串。状态定义和转移枚举分割点的方式非常相似。解码方法数字串解码成字母求解码方式总数。也是线性DP考虑当前位置与前一个位置的关系。识别出这类问题的共性——定义dp[i]为考虑前i个字符的最优解或方案数然后枚举最后一段的起点——是解决一大批字符串分割DP问题的钥匙。7. 性能优化与工程化考虑7.1 空间复杂度优化我们的DP使用了 O(n * k) 的空间。观察状态转移方程dp[i][j]只依赖于dp[0...i-1][j-1]即上一列j-1的数据。因此我们可以使用滚动数组将空间复杂度优化到 O(n)。具体做法是只维护两个一维数组prev和curr分别代表j-1列和j列。vectorlong long dp(n 1, 0); // 初始化 j0 列 for (int i 1; i n; i) { dp[i] numVal[0][i - 1]; } for (int j 1; j k; j) { vectorlong long new_dp(n 1, 0); // 注意i的起始至少需要 j1 个字符才能插入j个乘号 for (int i j 1; i n; i) { long long maxProd 0; for (int m j 1; m i; m) { long long curProd dp[m - 1] * numVal[m - 1][i - 1]; maxProd max(maxProd, curProd); } new_dp[i] maxProd; } dp move(new_dp); // 滚动到下一列 } return dp[n];注意在滚动数组实现中dp[i]在每一轮外循环固定j中代表的是“前i个字符插入当前考虑的乘号数量”的最大乘积。初始化dp为j0的情况。然后对于每个j我们计算新的new_dp计算完后将其赋给dp用于下一轮。同时i的循环可以从j1开始因为少于这个长度无法插入j个乘号。7.2 大数处理与高精度实现如果题目明确提示结果可能超过long long范围例如数字串长度上百就需要实现高精度乘法。我们可以用字符串或数组来表示大整数。dp数组和numVal数组都将存储大数对象。状态转移中的乘法变为高精度乘法。这会显著增加代码量但思路完全不变。在面试中除非特别说明否则通常不需要写高精度但可以口头讨论这种可能性。7.3 测试用例设计自己测试时要覆盖各种边界和特殊情况最小输入n1, k0。dp[1][0]应等于该数字本身。k0不插入任何乘号应返回整个字符串转换的数字。kn-1在每个空隙都插入乘号乘积等于各数字相乘。包含零的数字串如10203, k1。零会影响乘积需要算法正确处理。单调数字串如12345插入乘号时往往倾向于将大数尽量留在后面或前面可以手动验证。大数测试随机生成长度适中的数字串用暴力搜索小规模验证DP结果的正确性。8. 常见面试提问与回答思路如果你在面试中遇到这道题面试官可能会沿着以下路径追问Q: 请描述一下你的思路。A: 这是一个最优化问题暴力枚举所有插入位置组合不可行。我注意到问题具有最优子结构性质为了求前i个字符插入j个乘号的最大乘积可以枚举最后一个乘号的位置。假设最后一个乘号放在第m个字符后那么问题分解为求前m个字符插入j-1个乘号的最大乘积乘以最后一段字符代表的数字。这自然引导我用动态规划定义dp[i][j]用三重循环实现。Q: 时间复杂度是多少能优化吗A: 预处理子串数值O(n^2)DP过程三重循环O(n^2 * k)。在k接近n时是O(n^3)。对于给定的约束通常n50是可以接受的。空间复杂度O(n^2)可以优化到O(n)使用滚动数组。进一步的优化可能涉及利用数学性质比如对于正数乘积最大往往希望各部分尽可能均匀类似算术-几何平均不等式但字符串分割是离散的这个性质不能直接用来剪枝所以O(n^3)可能已是较优解。Q: 如果数字串很长比如n1000你的算法会有什么问题A: 主要问题是时间复杂度O(n^3)会达到10^9级别不可接受。空间复杂度O(n^2)也需要10^6的存储可能可以承受但效率低。对于更大的n可能需要更高效的算法或者题目会限制k很小比如k10这样复杂度是O(n^2 * k)或许可行。另一个问题是乘积可能极大需要高精度计算这又会增加常数时间。Q: 如何修改代码以输出插入乘号的具体位置A: 可以在DP过程中维护一个平行的数组cut[i][j]记录状态dp[i][j]取得最大值时最后一个乘号左边子串的长度或最后一个乘号的位置。DP结束后从cut[n][k]开始回溯递归地找到所有乘号的位置。Q: 这和矩阵链乘问题有什么相似之处A: 两者都是通过“枚举最后一次操作的位置”来划分问题。矩阵链乘是选择最后一次乘法的位置将矩阵链分成左右两部分分别计算左右部分的最少乘法次数然后加上合并的代价。插入乘号是枚举最后一个乘号的位置将字符串分成左右两部分分别计算左部分插入一定数量乘号的最大乘积然后乘以右部分的数值。状态转移方程的结构非常相似都是区间DP的经典形式。这道“插入乘号”的题目虽然代码实现只有几十行但它涵盖了动态规划的核心状态定义、转移方程、边界处理、优化技巧。理解透彻这一道题就能触类旁通解决一大类字符串分割最优化问题。在实际编写时务必注意内层循环的起始条件m j1和dp[0][0]的初始化这是通过手动调试一个小案例才能深刻领会的细节。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
