CS-Notes 剑指 Offer 第 14 题「剪绳子」贪心与动态规划双解法完整解析【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 notes/14. 剪绳子.md 展开完整覆盖原题的贪心策略数学证明、O(1) 贪心解法与 O(n²) 动态规划解法的 Java 实现。读完后你将理解「为什么最优拆分只能是 2 和 3 的组合」「为什么优先拆出 3」这一贪心结论的推导过程并能独立完成两种解法及其复杂度分析同时可对照仓库中同构的 LeetCode 343 题验证动态规划思路。一、题目描述与基本规则把一根绳子剪成多段使得每段长度的乘积最大。给定绳子长度n返回能得到的最大乘积。n 2 return 1 (2 1 1) n 10 return 36 (10 3 3 4)两个示例隐含了本题的两条基本规则也是后续代码中边界判断的来源绳子必须至少剪一刀即最终至少产生两段。n 2时只能拆成1 1乘积为 1而不是保留不拆得到 2每段长度都是正整数且不允许出现长度为 1 的段对n 4的情形而言这一点将在贪心证明中给出严格推导。该题在 剑指 Offer 题解 - 目录 中归类于「贪心思想」章节与「63. 股票的最大利润」并列是剑指 Offer 中少数同时适合用贪心和动态规划两种视角切入的题目之一。二、贪心策略先证明再写代码贪心解法的结论是尽可能多地剪出长度为 3 的绳子并且不允许出现长度为 1 的绳子。如果拆分过程中出现了 1就从已剪好的 3 中拿出一段与 1 重新组合把3 1改切为两段2 2因为2 × 2 3 × 1。这个结论不是凭直觉给出的原文档逐段给出了完整证明过程下面按「逐段试探」的思路完整继承并展开。设当前有一段长度为n的绳子考虑把它拆成k与n - k两段比较拆分后的乘积k(n - k)与不拆的n的大小2.1 长度 1绝对不能出现拆成1和n - 1则1 × (n - 1) - n -1 0拆开后的乘积一定比不拆更小所以任何最优方案中都不能出现长度为 1 的绳子n 2的1 1是「必须至少剪一刀」规则下的特例后面代码中单独处理。2.2 长度 2n 4 时拆了更优拆成2和n - 2则2(n - 2) - n n - 4。当n 4时该值为非负即这样拆能得到的乘积不小于不拆。所以从 4 开始拆出 2 总是有收益的。2.3 长度 3n 5 时比拆 2 更好拆成3和n - 3则3(n - 3) - n 2n - 9在n 5时效果更好。进一步比较拆 3 与拆 23(n - 3) - 2(n - 2) n - 5 0 n 5即在n 5的范围内每一步拆出 3 的收益都不低于拆出 2这是「优先拆 3」这一贪心选择的直接依据。2.4 长度 4、5、6 及更大都能被 2 和 3 支配拆 4因为4 2 × 2效果和拆成 2 一样不构成更优选项拆 55 2 3且5 2 × 3所以不能出现长度为 5 的绳子应尽可能拆成 2 和 3拆 66 3 3且6 3 × 3所以不能出现长度为 6 的绳子应拆成 3 和 3。虽然 6 也可以拆成2 2 2但由上面的比较3(n - 3) - 2(n - 2) n - 5 0可知在n 5时拆成 3 依然不差于拆成 2。继续尝试更大的段长可以发现效果都劣于拆成 2 和 3 的组合。由此得到贪心策略的完整表述只考虑把绳子拆成 2 和 3且优先拆 3唯一的例外是当剩余长度减到 4 时即即将出现3 1的局面不能继续拆 3而应直接拆成2 2。2.5 策略落地拆 3 的个数如何确定把上述策略翻译成计数问题。设 3 的段数为timesOf32 的段数为timesOf2先令timesOf3 n / 3整数除法尽可能多拆 3若余数为 1说明最后会剩3 1按 2.4 节结论需要回退timesOf3--把这段3 1改造成2 2此时余数变为 2恰好对应一个 2否则余数只能是 0 或 2timesOf2 (n - timesOf3 * 3) / 2最多得到 1 段 2余数 2 时或 0 段 2余数 0 时。用题目示例验证n拆分3 的段数2 的段数乘积21 1特判——131 2特判——242 2余数 1 回退02452 3116103 3 4余数 1 回退2236n 2、n 3之所以必须特判而不能套用「优先拆 3」因为题目要求至少剪一刀3 3不剪是不合法的只能拆成1 2得到 2。这也解释了为什么贪心策略中的「拆 3」只适用于n 4的情形。2.6 贪心 Java 实现完整继承原文档代码public int cutRope(int n) { if (n 2) return 0; if (n 2) return 1; if (n 3) return 2; int timesOf3 n / 3; if (n - timesOf3 * 3 1) timesOf3--; int timesOf2 (n - timesOf3 * 3) / 2; return (int) (Math.pow(3, timesOf3)) * (int) (Math.pow(2, timesOf2)); }逐段说明n 2返回 0小于 2 的绳子无法产生任何「至少两段」的合法拆分属于输入兜底n 2、n 3特判返回 1、2即 2.5 节讨论的「必须剪一刀」边界不能套用拆 3 策略n - timesOf3 * 3 1即余数为 1 的回退逻辑把3 1改写为2 2最终返回3^timesOf3 * 2^timesOf2。复杂度时间 O(1)Math.pow按常数复杂度计空间 O(1)。适用前提该实现用int存结果而答案量级约为 3^(n/3)随 n 增长非常快例如 n 50 时已达 10^8 量级n 100 时超过 int 上限。题目原题输入规模较小经典约束下为两位数以内int 足够若把此代码移植到允许大 n 的场景应改用long或按题目要求取模这一点使用时需要注意。三、动态规划解法不依赖贪心证明的通法如果面试现场无法完整复现贪心证明动态规划是更稳妥的保底解法。它不依赖任何数学结论直接枚举第一次剪在哪里。3.1 状态定义与转移方程设dp[i]为长度为i的绳子剪成至少两段后的最大长度乘积目标为dp[n]初始化dp[1] 1。对于长度i枚举第一刀位置j1 j i绳子被分成j和i - j两段。由于两侧对称只需考虑三种情形取最大两段都不再剪乘积为j * (i - j)左侧继续剪左侧取它的最优值dp[j]右侧不再剪乘积为dp[j] * (i - j)右侧继续剪的情形j * dp[i - j]与情形 2 对称j从 1 遍历到i - 1时已被覆盖无需单独枚举。于是转移方程为dp[i] max(dp[i], max(j * (i - j), dp[j] * (i - j)))对应原文档代码public int cutRope(int n) { int[] dp new int[n 1]; dp[1] 1; for (int i 2; i n; i) for (int j 1; j i; j) dp[i] Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j))); return dp[n]; }复杂度时间 O(n²)两层循环空间 O(n)。3.2 小例子手工推演n 10用转移方程逐步推演验证与题目示例36一致i关键转移dp[i]2j1: 1×113j1: 1×224j2: 2×245j2: 2×366j3: 3×397j4: 4×3128j4: 4×4169j6: dp[6]×3 9×32710j6: dp[6]×4 9×4等价于 33436可以看到dp[10] 36恰好来自「左侧最优拆成 33、右侧保留 4」这一转移与贪心解3 3 4殊途同归。这个推演也解释了转移方程的合理性dp[j] * (i - j)一项允许左侧被拆成多段等价于把「一次剪两刀甚至更多刀」压缩成了「第一刀切下 j剩余部分的最优拆法由 dp 记忆」。四、与同构题 LeetCode 343 Integer Break 的对照本题与 LeetCode 343Integer Break整数拆分题面几乎一致仓库中 Leetcode 题解 - 动态规划 收录了它的动态规划解法public int integerBreak(int n) { int[] dp new int[n 1]; dp[1] 1; for (int i 2; i n; i) { for (int j 1; j i - 1; j) { dp[i] Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j))); } } return dp[n]; }与剪绳子的 DP 写法相比二者状态定义相同、时间复杂度都是 O(n²)唯一的差异在于「继续剪」一侧的选择剪绳子版本写dp[j] * (i - j)继续剪左侧Integer Break 版本写j * dp[i - j]继续剪右侧。由于转移方程对左右两侧是对称的且j遍历了全部切点两种写法得到的dp数组完全相同结果一致。这个对照可以帮助理解这类「拆成多段求最大乘积」问题的 DP 骨架是稳定的贪心只是它在特殊结构段长为连续正整数下的闭式加速。五、小结两种解法怎么选维度贪心动态规划核心思想只拆 2 和 3优先拆 3余 1 时31改22枚举第一刀位置dp[i]记忆最优乘积时间复杂度O(1)O(n²)空间复杂度O(1)O(n)边界处理需特判n 2、n 3至少剪一刀由dp[1] 1与「必须剪一刀」的转移自然处理前置条件需要复现「1 不允许、优先拆 3」的数学证明无需证明状态转移可直接推出面试中的实用建议优先尝试写出贪心并口述第二节中的证明链1 不允许 → 拆 2/3 有效 → 3 优于 2 → 4/5/6 被 2 和 3 支配若证明卡壳立即切换到 DP 解法保底。两种解法在n 2、n 10上分别给出 1 和 36与原题示例一致可作为自测用例。更多同风格题解可参考仓库中的 剑指 Offer 题解 - 目录本题位于「贪心思想」分类以及 Leetcode 题解 - 动态规划。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考