刷东华大学OJ刷到第39题“最大乘积”时我一开始真没当回事。题面就一句话把一个正整数n拆成若干个正整数之和问这些正整数乘积的最大值是多少。当时我第一反应是DFS暴力枚举所有拆法第二反应是这不就是动态规划模板题吗。直到我看清数据范围、算了几组手写样例之后才发现这道题真正的考点根本不是代码能力而是你能不能从一堆“看起来都差不多”的拆分方案里看出3这个数字的特殊地位。这篇就把我从读题、推导、写代码到提交排错的全过程完整拆开讲内容包括最终结论的数学来源、不同数据范围下的代码选型、以及几个我实际提交时踩过、也看同学踩过的坑。不管你是刚接触OJ的新手还是刷题想提速的老手这题都值得彻底吃透。1. 先确认题面别把两个“最大乘积”搞混1.1 最常见题面整数拆分版“最大乘积”这名字在东华OJ、以及很多学校自建OJ里都出现过最常见的题面长这样输入一个正整数n将n拆分成至少两个正整数的和求这些正整数乘积的最大值。例如n10可以拆成334乘积为3×3×436。注意“至少两个正整数”这个限定非常关键。如果没有这个限定n本身就是一个合法的“拆法”那答案永远是n题目就没意义了。所以几乎所有OJ版本都会明确要求至少拆成两份或者等价地说“将一个正整数n分成若干个正整数之和这些数之和为n”。n10的时候拆法非常多19、28、226、235、334、2233……其中乘积最大的是334乘积36。你可以自己手算验证一下确实找不到比36更大的拆法。那问题来了这个“334”是拍脑袋凑出来的还是背后有规律1.2 数据范围决定你是用int还是大数这是最容易让新手直接翻车的地方。不同OJ上这道题给的数据范围差异非常大我见过三种版本n ≤ 20乘积上限不大int就够用n ≤ 60 或 n ≤ 100指数增长下long long在某些边界会爆n 达到几千甚至上万必须使用Python、Java BigInteger或手写高精度乘法。拿long long来说它的上限大约是9.22×10^18而3^40就约等于1.216×10^19已经超了。也就是说当n大到一定规模时你用C的long long直接乘结果可能是负数——这不是你代码逻辑写错了是类型容量不够了。所以动笔写代码之前先找题目原页看清楚n的范围再决定用哪种方案。下面是我整理的一个自查表对应不同n范围建议采用的写法n范围乘积上限估算建议方案n ≤ 203^6≈729int足够n ≤ 803^26≈2.54×10^12long long足够n ≤ 1103^36×2≈3.0×10^17long long可以扛n 110指数继续暴涨很快超过9.22×10^18Python / Java BigInteger / 高精度乘法这个表不是精确边界只是一个快速判断标准。等你读完后面的公式推导自然就明白我为什么用3的幂次来估算。1.3 输入输出格式也要一并看除了数据范围输入格式也经常有坑。有的OJ是单组数据读一个n就结束有的则是多组数据直到EOF还有的先给一个T表示测试组数。题目如果没写清楚建议默认按多组数据处理写while(scanf(%d, n) ! EOF)这种能同时兼容单组和多组的读法。输出上有的题目要求每个结果占一行有的要求带“Case #x:”前缀如果不带就判WA。这些信息都在题面的输入输出描述里刷题老手都知道读题比写代码花的时间多才是正常的。2. 从枚举开始乘积的变化里藏着规律2.1 手算前几项先建立直觉我当时拿到题没有直接去套算法而是先在小本子上列了一个表把n2到n12的最优拆法和最大乘积全部手算出来。这个过程太重要了强烈建议你每次遇到这类“找最优”的题也这么干。n最优拆法示例最大乘积21113122422452366339734或3221283321893332710334361133325412333381观察这张表能看出几个非常明显的特点最优拆法里的每个因子都很小集中在2、3、4这几个数字没有出现5、6、7这样的大因子因子中出现过4但4又等价于22所以本质上只用到了2和3随着n越来越大拆出来的3越来越多2最多只出现两次。这些现象不是巧合它们共同指向一个结论乘积最大的拆法就是尽可能多地拆出3。2.2 为什么因子都是小数这不是巧合很多人看到“尽量拆3”这个结论第一反应是“为什么不是拆2拆2不是更平均吗”如果你也这么想说明还没抓到问题的本质。我们来看一个关键的不等式对于任意大于等于5的整数a把它拆成3和a-3之后乘积会变成3(a-3)需要比较的是3(a-3)和原来的a到底谁大。3(a-3) 3a - 9当a≥5时3a-9 a因为2a 9在a≥5时恒成立。也就是说任何大于4的因子都可以通过拆出一个3让乘积变得更大。一直拆下去最优解里就不可能存在5及以上的因子。这个证明非常朴素但它直接锁定了因子的范围只可能在1、2、3、4里面选。因子1显然没有贡献——把一个1并到其他因子b上乘积从1×b变成b1变大了所以最优解里也不会有1除非是n2、3这种退化情况。于是真正需要讨论的只剩2、3、4。而4又能拆成22乘积不变。到这里最优解的因子集合就被压缩到了2和3两个数字。2.3 余数分类三类情况对应三个答案明确了最优解只由2和3组成之后下一步是确定2和3的个数配比。这里有一个很漂亮的比较2×2×2 83×3 9同样是凑出总和6三个2的乘积是8两个3的乘积是9。换句话说只要出现三个2就可以把它替换成两个3乘积反而更大。所以在最优解里2的个数最多只能有2个。到此最优解的结构彻底清晰若干个3再加上最多两个2。具体是哪种组合取决于n除以3的余数。设k n // 3整除向下取整余数r n % 3那么余数拆法结构最大乘积r0全部拆成3共k个3^kr1拆成k-1个3和两个2等价于一个43^(k-1)×4r2拆成k个3和一个23^k×2以n10为例k3r1所以拆成2个3和1个4即334乘积36与枚举结果完全一致。n11k3r2拆成3个3和1个2乘积54。n12k4r0全部拆成3乘积81。3. 更严谨的推导为什么“尽量拆3”是最优解3.1 用均值不等式理解3的来源上面基于不等式的证明已经足够严谨但如果你想从更深的层面理解“为什么偏偏是3”这里还有一个非常漂亮的视角。假设我们把n拆成了m个数它们的和固定为n。根据均值不等式当这m个数彼此相等时乘积最大。如果每个数都等于x那么x n/m乘积大约等于x^m (n/m)^m。现在把m当作自由变量。令f(m) m·ln(n/m)求导后令其为0解出来的最优m n/e也就是说每个数约等于e≈2.71828。e是自然常数最接近它的正整数就是3。这就是“尽量拆3”背后的数学直觉来源连续情形下的最优值是e离散化之后自然落在3上。这个视角虽然不能作为严格证明但它能帮你记住结论也能解释为什么不是2也不是4。3.2 两道不等式锁死因子结构如果你需要在题解里写出严格证明下面这两个引理就够了引理一最优拆分中不会出现大于4的因子。证设某因子为a≥5将其替换为3和a-3。新乘积与原乘积之比为[3(a-3)]/a 3 - 9/a。当a≥5时3 - 9/a ≥ 3 - 9/5 1.2 1即新乘积严格变大与最优矛盾。引理二最优拆分中2的个数不超过2个。证若出现3个2它们的和为6、乘积为8。用两个3替换后和仍为6但乘积变为9严格变大与最优矛盾。这两个引理直接把最优解限制成了“若干3加上至多两个2”的形态。再结合n模3的余数分类就得到了第2节末尾的完整公式。这套证明只有几行却能一步到位是这道题最精华的部分。3.3 用动态规划交叉验证公式数学推导再漂亮提交之前我也习惯写一个暴力DP来对拍。一是确认公式没有在小数据上出错二是如果手头有别人的题解可以快速验证它的正确性。这道题的动态规划思路本身也值得一写定义dp[i]表示正整数i拆分后能得到的最大乘积。注意我们强制要求i至少被拆成两份所以在状态转移时要保证至少有一个部分不再拆分。转移方程dp[i] max(dp[p] × (i-p), p × (i-p))其中1 ≤ p i这里取max(dp[p], p)是因为p可以选择“继续拆”或“保持原样”而i-p这一部分我们固定不拆以此保证整份拆分至少有两部分。初始值dp[1]1。C的对照代码如下#include bits/stdc.h using namespace std; long long bruteForce(int n) { vectorlong long dp(n 1, 0); dp[1] 1; for (int i 2; i n; i) { for (int p 1; p i; p) { long long left max(dp[p], (long long)p); dp[i] max(dp[i], left * (i - p)); } } return dp[n]; } long long formula(int n) { if (n 2) return 1; if (n 3) return 2; int k n / 3; int r n % 3; if (r 0) return pow(3, k); if (r 1) return pow(3, k - 1) * 4; return pow(3, k) * 2; } int main() { for (int n 2; n 50; n) { if (bruteForce(n) ! formula(n)) { cout mismatch at n endl; return 0; } } cout all ok endl; return 0; }我实测过n2到n50公式法和DP的结果完全一致。这个对拍过程强烈推荐尤其是你在考场或OJ上对数学结论不够有把握的时候。DP代码虽然复杂度是O(n^2)但作为小数据验证工具非常可靠。4. 代码落地从公式到AC代码4.1 最简单的循环写法公式虽然直观但真写到代码里还有一个更不容易出错的迭代写法很多人叫它“减3法”。代码逻辑是只要当前n大于4就乘一个3然后让n减3最后再把剩下的数乘进去。#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF) { if (n 3) { printf(%d\n, n - 1); continue; } long long ans 1; while (n 4) { ans * 3; n - 3; } ans * n; printf(%lld\n, ans); } return 0; }这个写法为什么可行我们模拟一遍n554ans3n2退出循环ans3×26n664ans3n3退出循环ans3×39n774ans3n4退出循环ans3×412n884ans3n554ans9n2退出ans9×218。本质上这个循环就是把“能拆3就拆3”这句话原封不动翻译成了代码。它的好处是避免了手动处理n%31时需要特判“少用一个3换成两个2”的细节——循环跑到最后剩下的数要么是4要么是3要么是2直接乘上去就行。4.2 快速幂版本如果n的范围很大比如n可以到10^9while循环每次减3就太慢了需要用快速幂直接计算3^k。C语言版本long long qpow(long long a, long long b) { long long res 1; while (b) { if (b 1) res * a; a * a; b 1; } return res; } long long maxProduct(int n) { if (n 2) return 1; if (n 3) return 2; int k n / 3; int r n % 3; if (r 0) return qpow(3, k); if (r 1) return qpow(3, k - 1) * 4; return qpow(3, k) * 2; }快速幂本身不复杂复杂度降到O(log n)。需要说明的是绝大多数OJ上这道题的n不会给到10^9这么大因为结果会长到根本没法输出了。所以快速幂更多是为了应对“n很大但取模”的变体题比如要求结果模1000000007这时公式照用乘法换成模乘即可。4.3 需要大数时怎么办如果题目数据范围阴险n给到几百甚至上千long long完全不够这时有两条路用Python。Python的整数是任意精度的代码最简单import sys def solve(n: int) - int: if n 2: return 1 if n 3: return 2 k, r divmod(n, 3) if r 0: return 3 ** k if r 1: return 3 ** (k - 1) * 4 return 3 ** k * 2 for line in sys.stdin: print(solve(int(line.strip())))用Java的BigIntegerimport java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextInt()) { int n sc.nextInt(); if (n 2) { System.out.println(1); } else if (n 3) { System.out.println(2); } else { int k n / 3; int r n % 3; BigInteger ans; if (r 0) { ans BigInteger.valueOf(3).pow(k); } else if (r 1) { ans BigInteger.valueOf(3).pow(k - 1).multiply(BigInteger.valueOf(4)); } else { ans BigInteger.valueOf(3).pow(k).multiply(BigInteger.valueOf(2)); } System.out.println(ans); } } sc.close(); } }我个人的习惯是如果OJ支持Python这类大数题直接用Python写省去手写高精度乘法的所有烦恼。C也不是不能写用字符串存每一位做高精度乘3总共也就几十行但没必要在这种入门题上跟自己较劲。4.4 取模变体要注意什么有些进阶版的题目会要求输出乘积对1000000007取模的结果。这种情况下公式不变但所有乘法都要换成模乘。比如计算3^k时用快速幂取模const long long MOD 1000000007L; long long qpow(long long a, long long b) { long long res 1; while (b) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; }再提醒一个细节c语言里printf输出long long要用%lldscanf输入int要用%d这个看似基础但每年都有不少人在这些细节上浪费好几发提交。多组输入时每行结尾记得换行。5. 提交OJ的排错链路WA之后我查了哪些东西5.1 把WA分成“思路错”和“实现错”两类第一次提交如果返回WA先冷静下来别急着改代码。我通常按以下顺序排查重新读题面确认输入格式和输出格式检查是不是把“至少拆成两份”理解漏了检查边界casen2、n3、n4检查数据类型溢出检查多组输入是否用了正确的循环最后再怀疑公式本身。思路错和实现错是完全不同的两类问题。公式用错你会看到小数据都过不了数据类型溢出你会看到小数据都对、一到n稍大就输出负数或随机数。5.2 边界case自测清单我在本地提交之前一定会跑这张自测表。你可以直接抄下来当模板n预期输出常见错误输出及原因21输出2没有强制拆分32输出3没有强制拆分44输出3余数1时误写成3^(k-1)×356输出5没有拆分69输出8错拆成2221036输出27把余数1当成1333处理这里面n10的错误最有代表性。很多新手拿到公式后余数1的情况直接写3^(k-1)×3×1也就是把10拆成3331乘积27。但正确做法是把那个1和一个3合并成4也就是334乘积36。记住余数为1时不是“少一个3再补一个1”而是“少一个3改成两个2”因为2×24 3×13。5.3 一个容易阴沟翻船的溢出实例long long溢出这个问题特别想举一个真实例子。n118时k39r1公式是3^39×4。3^39约等于4.0526×10^18再乘4之后约等于1.621×10^19已经超过long long上限9.22×10^18结果会溢出成负数。更有意思的是n119k39r2公式是3^39×2约等于8.105×10^18还在long long范围内能正常输出。也就是说118溢出、119正常、120又溢出3^40约1.216×10^19。就差1结果天上地下。遇到这种边界如果你不想费劲去算3的幂次最稳妥的方案就是判断n的范围超过110直接用Python或Java。如果你必须用C可以先通分化简比如r1时先算3^(k-1)再乘4最后再判断是否超过某个阈值但这样代码就绕了不如换语言。5.4 TLE在这题基本不存在但别忽略读入方式“最大乘积”这道题在算法上几乎没有超时的可能公式法O(1)或O(log n)都很快。如果真遇到TLE要么是n极大且你用了while减3的循环要么是代码里有别的问题。比如多组输入时用了printf逐字符输出大数而不是一次println。在高精度场景下过度使用字符串拼接也是个常见性能杀手。6. 跟“最大乘积”沾边的变形题6.1 数字串插入K个乘号经典区间DP如果你在东华OJ或其它OJ上搜“最大乘积”还可能看到另一个题面给定一个数字串要求往里插入K个乘号把它分成K1段求这K1段数的乘积的最大值。比如数字串“1231”K1可以拆成1×231231、12×31372、123×1123最大值372。这个版本和整数拆分的解法完全不同它是一道典型的区间DP题。设dp[i][j]表示前i位数字用了j个乘号得到的最大乘积num[l][r]表示数字串第l到第r位截出来的整数转移方程是dp[i][j] max(dp[p][j-1] × num[p1][i])其中p从j遍历到i-1for (int i 1; i len; i) { dp[i][0] num[1][i]; } for (int j 1; j k; j) { for (int i j 1; i len; i) { for (int p j; p i; p) { dp[i][j] max(dp[i][j], dp[p][j - 1] * num[p 1][i]); } } }这道题同样叫“最大乘积”或“乘积最大”很容易和整数拆分版混淆。做题前一定要先看题面是给你一个整数n还是给你一个数字串和乘号数量K。这两者的解法和复杂度完全不同。6.2 LeetCode 343 整数拆分 / 剑指Offer 剪绳子LeetCode 343题“整数拆分”和剑指Offer的“剪绳子”本质上就是这道题把正整数n拆成至少两个正整数求最大乘积。解法完全一样核心结论都是“尽量拆3”。所以如果你今天把这篇的内容消化透了这三道题等于同时AC。LeetCode 343的约束n最大58int甚至都够用剪绳子在牛客网那个版本n最大60long long也能轻松覆盖。6.3 贪心失效的场景最后说一个重要的事情这个贪心策略有严格的前提——拆分的份数不限、每份没有上限、顺序无关。一旦题目换了限制条件公式就不能直接套了。比如要求必须拆成恰好3个数n11时最优拆法是344乘积48而不是3332的54因为后者是4个数不满足约束。再比如要求每个拆分出来的数不能超过某个上限M当M小于3时“尽量拆3”就直接报废要改用动态规划或数学规划。所以我的建议是公式要背但更要把公式的推导过程记住。我后来刷题养成了一个习惯遇到这类“最优化拆分”的题先枚举小数据找规律再用不等式或对拍程序验证结论最后写代码提交。这个过程本身比记住一个结论有用得多。最大乘积这道题是我刷OJ早期印象很深的一道也是我认为最适合用来建立“数学分析优先于代码实现”这一意识的一道题。希望这篇能把这种思维也传递给你。
刷东华大学OJ刷到第39题“最大乘积”时我一开始真没当回事。题面就一句话把一个正整数n拆成若干个正整数之和问这些正整数乘积的最大值是多少。当时我第一反应是DFS暴力枚举所有拆法第二反应是这不就是动态规划模板题吗。直到我看清数据范围、算了几组手写样例之后才发现这道题真正的考点根本不是代码能力而是你能不能从一堆“看起来都差不多”的拆分方案里看出3这个数字的特殊地位。这篇就把我从读题、推导、写代码到提交排错的全过程完整拆开讲内容包括最终结论的数学来源、不同数据范围下的代码选型、以及几个我实际提交时踩过、也看同学踩过的坑。不管你是刚接触OJ的新手还是刷题想提速的老手这题都值得彻底吃透。1. 先确认题面别把两个“最大乘积”搞混1.1 最常见题面整数拆分版“最大乘积”这名字在东华OJ、以及很多学校自建OJ里都出现过最常见的题面长这样输入一个正整数n将n拆分成至少两个正整数的和求这些正整数乘积的最大值。例如n10可以拆成334乘积为3×3×436。注意“至少两个正整数”这个限定非常关键。如果没有这个限定n本身就是一个合法的“拆法”那答案永远是n题目就没意义了。所以几乎所有OJ版本都会明确要求至少拆成两份或者等价地说“将一个正整数n分成若干个正整数之和这些数之和为n”。n10的时候拆法非常多19、28、226、235、334、2233……其中乘积最大的是334乘积36。你可以自己手算验证一下确实找不到比36更大的拆法。那问题来了这个“334”是拍脑袋凑出来的还是背后有规律1.2 数据范围决定你是用int还是大数这是最容易让新手直接翻车的地方。不同OJ上这道题给的数据范围差异非常大我见过三种版本n ≤ 20乘积上限不大int就够用n ≤ 60 或 n ≤ 100指数增长下long long在某些边界会爆n 达到几千甚至上万必须使用Python、Java BigInteger或手写高精度乘法。拿long long来说它的上限大约是9.22×10^18而3^40就约等于1.216×10^19已经超了。也就是说当n大到一定规模时你用C的long long直接乘结果可能是负数——这不是你代码逻辑写错了是类型容量不够了。所以动笔写代码之前先找题目原页看清楚n的范围再决定用哪种方案。下面是我整理的一个自查表对应不同n范围建议采用的写法n范围乘积上限估算建议方案n ≤ 203^6≈729int足够n ≤ 803^26≈2.54×10^12long long足够n ≤ 1103^36×2≈3.0×10^17long long可以扛n 110指数继续暴涨很快超过9.22×10^18Python / Java BigInteger / 高精度乘法这个表不是精确边界只是一个快速判断标准。等你读完后面的公式推导自然就明白我为什么用3的幂次来估算。1.3 输入输出格式也要一并看除了数据范围输入格式也经常有坑。有的OJ是单组数据读一个n就结束有的则是多组数据直到EOF还有的先给一个T表示测试组数。题目如果没写清楚建议默认按多组数据处理写while(scanf(%d, n) ! EOF)这种能同时兼容单组和多组的读法。输出上有的题目要求每个结果占一行有的要求带“Case #x:”前缀如果不带就判WA。这些信息都在题面的输入输出描述里刷题老手都知道读题比写代码花的时间多才是正常的。2. 从枚举开始乘积的变化里藏着规律2.1 手算前几项先建立直觉我当时拿到题没有直接去套算法而是先在小本子上列了一个表把n2到n12的最优拆法和最大乘积全部手算出来。这个过程太重要了强烈建议你每次遇到这类“找最优”的题也这么干。n最优拆法示例最大乘积21113122422452366339734或3221283321893332710334361133325412333381观察这张表能看出几个非常明显的特点最优拆法里的每个因子都很小集中在2、3、4这几个数字没有出现5、6、7这样的大因子因子中出现过4但4又等价于22所以本质上只用到了2和3随着n越来越大拆出来的3越来越多2最多只出现两次。这些现象不是巧合它们共同指向一个结论乘积最大的拆法就是尽可能多地拆出3。2.2 为什么因子都是小数这不是巧合很多人看到“尽量拆3”这个结论第一反应是“为什么不是拆2拆2不是更平均吗”如果你也这么想说明还没抓到问题的本质。我们来看一个关键的不等式对于任意大于等于5的整数a把它拆成3和a-3之后乘积会变成3(a-3)需要比较的是3(a-3)和原来的a到底谁大。3(a-3) 3a - 9当a≥5时3a-9 a因为2a 9在a≥5时恒成立。也就是说任何大于4的因子都可以通过拆出一个3让乘积变得更大。一直拆下去最优解里就不可能存在5及以上的因子。这个证明非常朴素但它直接锁定了因子的范围只可能在1、2、3、4里面选。因子1显然没有贡献——把一个1并到其他因子b上乘积从1×b变成b1变大了所以最优解里也不会有1除非是n2、3这种退化情况。于是真正需要讨论的只剩2、3、4。而4又能拆成22乘积不变。到这里最优解的因子集合就被压缩到了2和3两个数字。2.3 余数分类三类情况对应三个答案明确了最优解只由2和3组成之后下一步是确定2和3的个数配比。这里有一个很漂亮的比较2×2×2 83×3 9同样是凑出总和6三个2的乘积是8两个3的乘积是9。换句话说只要出现三个2就可以把它替换成两个3乘积反而更大。所以在最优解里2的个数最多只能有2个。到此最优解的结构彻底清晰若干个3再加上最多两个2。具体是哪种组合取决于n除以3的余数。设k n // 3整除向下取整余数r n % 3那么余数拆法结构最大乘积r0全部拆成3共k个3^kr1拆成k-1个3和两个2等价于一个43^(k-1)×4r2拆成k个3和一个23^k×2以n10为例k3r1所以拆成2个3和1个4即334乘积36与枚举结果完全一致。n11k3r2拆成3个3和1个2乘积54。n12k4r0全部拆成3乘积81。3. 更严谨的推导为什么“尽量拆3”是最优解3.1 用均值不等式理解3的来源上面基于不等式的证明已经足够严谨但如果你想从更深的层面理解“为什么偏偏是3”这里还有一个非常漂亮的视角。假设我们把n拆成了m个数它们的和固定为n。根据均值不等式当这m个数彼此相等时乘积最大。如果每个数都等于x那么x n/m乘积大约等于x^m (n/m)^m。现在把m当作自由变量。令f(m) m·ln(n/m)求导后令其为0解出来的最优m n/e也就是说每个数约等于e≈2.71828。e是自然常数最接近它的正整数就是3。这就是“尽量拆3”背后的数学直觉来源连续情形下的最优值是e离散化之后自然落在3上。这个视角虽然不能作为严格证明但它能帮你记住结论也能解释为什么不是2也不是4。3.2 两道不等式锁死因子结构如果你需要在题解里写出严格证明下面这两个引理就够了引理一最优拆分中不会出现大于4的因子。证设某因子为a≥5将其替换为3和a-3。新乘积与原乘积之比为[3(a-3)]/a 3 - 9/a。当a≥5时3 - 9/a ≥ 3 - 9/5 1.2 1即新乘积严格变大与最优矛盾。引理二最优拆分中2的个数不超过2个。证若出现3个2它们的和为6、乘积为8。用两个3替换后和仍为6但乘积变为9严格变大与最优矛盾。这两个引理直接把最优解限制成了“若干3加上至多两个2”的形态。再结合n模3的余数分类就得到了第2节末尾的完整公式。这套证明只有几行却能一步到位是这道题最精华的部分。3.3 用动态规划交叉验证公式数学推导再漂亮提交之前我也习惯写一个暴力DP来对拍。一是确认公式没有在小数据上出错二是如果手头有别人的题解可以快速验证它的正确性。这道题的动态规划思路本身也值得一写定义dp[i]表示正整数i拆分后能得到的最大乘积。注意我们强制要求i至少被拆成两份所以在状态转移时要保证至少有一个部分不再拆分。转移方程dp[i] max(dp[p] × (i-p), p × (i-p))其中1 ≤ p i这里取max(dp[p], p)是因为p可以选择“继续拆”或“保持原样”而i-p这一部分我们固定不拆以此保证整份拆分至少有两部分。初始值dp[1]1。C的对照代码如下#include bits/stdc.h using namespace std; long long bruteForce(int n) { vectorlong long dp(n 1, 0); dp[1] 1; for (int i 2; i n; i) { for (int p 1; p i; p) { long long left max(dp[p], (long long)p); dp[i] max(dp[i], left * (i - p)); } } return dp[n]; } long long formula(int n) { if (n 2) return 1; if (n 3) return 2; int k n / 3; int r n % 3; if (r 0) return pow(3, k); if (r 1) return pow(3, k - 1) * 4; return pow(3, k) * 2; } int main() { for (int n 2; n 50; n) { if (bruteForce(n) ! formula(n)) { cout mismatch at n endl; return 0; } } cout all ok endl; return 0; }我实测过n2到n50公式法和DP的结果完全一致。这个对拍过程强烈推荐尤其是你在考场或OJ上对数学结论不够有把握的时候。DP代码虽然复杂度是O(n^2)但作为小数据验证工具非常可靠。4. 代码落地从公式到AC代码4.1 最简单的循环写法公式虽然直观但真写到代码里还有一个更不容易出错的迭代写法很多人叫它“减3法”。代码逻辑是只要当前n大于4就乘一个3然后让n减3最后再把剩下的数乘进去。#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF) { if (n 3) { printf(%d\n, n - 1); continue; } long long ans 1; while (n 4) { ans * 3; n - 3; } ans * n; printf(%lld\n, ans); } return 0; }这个写法为什么可行我们模拟一遍n554ans3n2退出循环ans3×26n664ans3n3退出循环ans3×39n774ans3n4退出循环ans3×412n884ans3n554ans9n2退出ans9×218。本质上这个循环就是把“能拆3就拆3”这句话原封不动翻译成了代码。它的好处是避免了手动处理n%31时需要特判“少用一个3换成两个2”的细节——循环跑到最后剩下的数要么是4要么是3要么是2直接乘上去就行。4.2 快速幂版本如果n的范围很大比如n可以到10^9while循环每次减3就太慢了需要用快速幂直接计算3^k。C语言版本long long qpow(long long a, long long b) { long long res 1; while (b) { if (b 1) res * a; a * a; b 1; } return res; } long long maxProduct(int n) { if (n 2) return 1; if (n 3) return 2; int k n / 3; int r n % 3; if (r 0) return qpow(3, k); if (r 1) return qpow(3, k - 1) * 4; return qpow(3, k) * 2; }快速幂本身不复杂复杂度降到O(log n)。需要说明的是绝大多数OJ上这道题的n不会给到10^9这么大因为结果会长到根本没法输出了。所以快速幂更多是为了应对“n很大但取模”的变体题比如要求结果模1000000007这时公式照用乘法换成模乘即可。4.3 需要大数时怎么办如果题目数据范围阴险n给到几百甚至上千long long完全不够这时有两条路用Python。Python的整数是任意精度的代码最简单import sys def solve(n: int) - int: if n 2: return 1 if n 3: return 2 k, r divmod(n, 3) if r 0: return 3 ** k if r 1: return 3 ** (k - 1) * 4 return 3 ** k * 2 for line in sys.stdin: print(solve(int(line.strip())))用Java的BigIntegerimport java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextInt()) { int n sc.nextInt(); if (n 2) { System.out.println(1); } else if (n 3) { System.out.println(2); } else { int k n / 3; int r n % 3; BigInteger ans; if (r 0) { ans BigInteger.valueOf(3).pow(k); } else if (r 1) { ans BigInteger.valueOf(3).pow(k - 1).multiply(BigInteger.valueOf(4)); } else { ans BigInteger.valueOf(3).pow(k).multiply(BigInteger.valueOf(2)); } System.out.println(ans); } } sc.close(); } }我个人的习惯是如果OJ支持Python这类大数题直接用Python写省去手写高精度乘法的所有烦恼。C也不是不能写用字符串存每一位做高精度乘3总共也就几十行但没必要在这种入门题上跟自己较劲。4.4 取模变体要注意什么有些进阶版的题目会要求输出乘积对1000000007取模的结果。这种情况下公式不变但所有乘法都要换成模乘。比如计算3^k时用快速幂取模const long long MOD 1000000007L; long long qpow(long long a, long long b) { long long res 1; while (b) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; }再提醒一个细节c语言里printf输出long long要用%lldscanf输入int要用%d这个看似基础但每年都有不少人在这些细节上浪费好几发提交。多组输入时每行结尾记得换行。5. 提交OJ的排错链路WA之后我查了哪些东西5.1 把WA分成“思路错”和“实现错”两类第一次提交如果返回WA先冷静下来别急着改代码。我通常按以下顺序排查重新读题面确认输入格式和输出格式检查是不是把“至少拆成两份”理解漏了检查边界casen2、n3、n4检查数据类型溢出检查多组输入是否用了正确的循环最后再怀疑公式本身。思路错和实现错是完全不同的两类问题。公式用错你会看到小数据都过不了数据类型溢出你会看到小数据都对、一到n稍大就输出负数或随机数。5.2 边界case自测清单我在本地提交之前一定会跑这张自测表。你可以直接抄下来当模板n预期输出常见错误输出及原因21输出2没有强制拆分32输出3没有强制拆分44输出3余数1时误写成3^(k-1)×356输出5没有拆分69输出8错拆成2221036输出27把余数1当成1333处理这里面n10的错误最有代表性。很多新手拿到公式后余数1的情况直接写3^(k-1)×3×1也就是把10拆成3331乘积27。但正确做法是把那个1和一个3合并成4也就是334乘积36。记住余数为1时不是“少一个3再补一个1”而是“少一个3改成两个2”因为2×24 3×13。5.3 一个容易阴沟翻船的溢出实例long long溢出这个问题特别想举一个真实例子。n118时k39r1公式是3^39×4。3^39约等于4.0526×10^18再乘4之后约等于1.621×10^19已经超过long long上限9.22×10^18结果会溢出成负数。更有意思的是n119k39r2公式是3^39×2约等于8.105×10^18还在long long范围内能正常输出。也就是说118溢出、119正常、120又溢出3^40约1.216×10^19。就差1结果天上地下。遇到这种边界如果你不想费劲去算3的幂次最稳妥的方案就是判断n的范围超过110直接用Python或Java。如果你必须用C可以先通分化简比如r1时先算3^(k-1)再乘4最后再判断是否超过某个阈值但这样代码就绕了不如换语言。5.4 TLE在这题基本不存在但别忽略读入方式“最大乘积”这道题在算法上几乎没有超时的可能公式法O(1)或O(log n)都很快。如果真遇到TLE要么是n极大且你用了while减3的循环要么是代码里有别的问题。比如多组输入时用了printf逐字符输出大数而不是一次println。在高精度场景下过度使用字符串拼接也是个常见性能杀手。6. 跟“最大乘积”沾边的变形题6.1 数字串插入K个乘号经典区间DP如果你在东华OJ或其它OJ上搜“最大乘积”还可能看到另一个题面给定一个数字串要求往里插入K个乘号把它分成K1段求这K1段数的乘积的最大值。比如数字串“1231”K1可以拆成1×231231、12×31372、123×1123最大值372。这个版本和整数拆分的解法完全不同它是一道典型的区间DP题。设dp[i][j]表示前i位数字用了j个乘号得到的最大乘积num[l][r]表示数字串第l到第r位截出来的整数转移方程是dp[i][j] max(dp[p][j-1] × num[p1][i])其中p从j遍历到i-1for (int i 1; i len; i) { dp[i][0] num[1][i]; } for (int j 1; j k; j) { for (int i j 1; i len; i) { for (int p j; p i; p) { dp[i][j] max(dp[i][j], dp[p][j - 1] * num[p 1][i]); } } }这道题同样叫“最大乘积”或“乘积最大”很容易和整数拆分版混淆。做题前一定要先看题面是给你一个整数n还是给你一个数字串和乘号数量K。这两者的解法和复杂度完全不同。6.2 LeetCode 343 整数拆分 / 剑指Offer 剪绳子LeetCode 343题“整数拆分”和剑指Offer的“剪绳子”本质上就是这道题把正整数n拆成至少两个正整数求最大乘积。解法完全一样核心结论都是“尽量拆3”。所以如果你今天把这篇的内容消化透了这三道题等于同时AC。LeetCode 343的约束n最大58int甚至都够用剪绳子在牛客网那个版本n最大60long long也能轻松覆盖。6.3 贪心失效的场景最后说一个重要的事情这个贪心策略有严格的前提——拆分的份数不限、每份没有上限、顺序无关。一旦题目换了限制条件公式就不能直接套了。比如要求必须拆成恰好3个数n11时最优拆法是344乘积48而不是3332的54因为后者是4个数不满足约束。再比如要求每个拆分出来的数不能超过某个上限M当M小于3时“尽量拆3”就直接报废要改用动态规划或数学规划。所以我的建议是公式要背但更要把公式的推导过程记住。我后来刷题养成了一个习惯遇到这类“最优化拆分”的题先枚举小数据找规律再用不等式或对拍程序验证结论最后写代码提交。这个过程本身比记住一个结论有用得多。最大乘积这道题是我刷OJ早期印象很深的一道也是我认为最适合用来建立“数学分析优先于代码实现”这一意识的一道题。希望这篇能把这种思维也传递给你。
