剑指offer-71、剪绳子（进阶版）
<h2 id="题描述">题⽬描述</h2><p>给你⼀根⻓度为 n 的绳⼦，请把绳⼦剪成整数⻓的 m 段（ m 、 n 都是整数， n > 1 并且 m ><br>
1 ， m <= n ），每段绳⼦的⻓度记为 k ,..., k 。请问 k * k * ... * k 可能的最⼤乘积是多少？例如，当绳⼦的⻓度是 8 时，我们把它剪成⻓度分别为 2 、3 、3 的三段，此时得到的最⼤乘积是 18 。</p>
<p>由于答案过⼤，请对 998244353 取模。</p>
<h2 id="思路解答">思路解答</h2>
<h3 id="动态规划">动态规划</h3>
<p>自底向上计算最优解</p>
<pre><code class="language-java">public class Solution {
private static final int MOD = 998244353;
public int cutRope(int n) {
if (n < 2) return 0;
if (n == 2) return 1;
if (n == 3) return 2;
// dp表示长度为i的绳子剪裁后的最大乘积
long[] dp = new long;
// 基础情况：这些值不是乘积，而是长度本身（因为可以不剪）
dp = 0;
dp = 1;
dp = 2;
dp = 3;
// 从长度为4开始计算
for (int i = 4; i <= n; i++) {
long max = 0;
// 遍历所有可能的分割点，j <= i/2 避免重复计算
for (int j = 1; j <= i / 2; j++) {
// 比较各种分割方案的乘积
long product = dp * dp;
if (product > max) {
max = product;
}
}
dp = max % MOD;
}
return (int) dp;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，外层循环n-3次，内层循环i/2次</li>
<li><strong>空间复杂度</strong>：O(n)，需要dp数组存储中间结果</li>
</ul>
<h3 id="优化动态规划">优化动态规划</h3>
<p>在上面版本上优化状态转移方程，提高代码效率，直接比较<code>j*(i-j)</code>和<code>j*dp</code>的最大值</p>
<p>dp = max(max(j × (i-j), j × dp)) 其中 1 ≤ j < i</p>
<ul>
<li>j × (i-j)：剪一刀的情况</li>
<li>j × dp：剪多刀的情况</li>
</ul>
<pre><code class="language-java">public class Solution {
private static final int MOD = 998244353;
public int cutRope(int n) {
if (n < 2) return 0;
if (n == 2) return 1;
if (n == 3) return 2;
long[] dp = new long;
dp = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
// 三种情况取最大值：不剪、剪一刀、剪多刀
long temp = Math.max(j * (i - j), j * dp);
dp = Math.max(dp, temp);
}
dp %= MOD;
}
return (int) dp;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，双重循环</li>
<li><strong>空间复杂度</strong>：O(n)，dp数组空间</li>
</ul>
<h3 id="贪心算法最优解">贪心算法（最优解）</h3>
<p>我们仔细观察就会发现：要想乘积⽐较⼤，在没有1的前提下，优先使⽤3，如果出现1，那么优先使⽤2</p>
<p>⽐如：</p>
<pre><code class="language-text">2 = 1 + 1
3 = 1 + 2
4 = 2 + 2
5 = 2 + 3
6 = 3 + 3
7 = 3 + 2 + 2
8 = 3 + 3 + 2
9 = 3 + 3 + 3
10 = 3 + 3 + 2 + 2
11 = 3 + 3 + 3 + 2
12 = 3 + 3 + 3 + 3
</code></pre>
<pre><code class="language-java">public class Solution {
public long cutRope(long number) {
if (number == 2) return 1;
if (number == 3) return 2;
long res = 1;
while (number > 4) {
res *= 3;
res = res % 998244353;
number -= 3;
}
return res * number % 998244353;
}
}
</code></pre>
<p>结果很不幸：运⾏超时：您的程序未能在规定时间内运⾏结束，请检查是否循环有错或算法复杂度过⼤。</p>
<p>于是我们需要想到其他的⽅式，如何快速计算 3 的 n 次⽅，这是我们需要解决的问题，因为在尽量凑 3的前提下，有以下三种情况：</p>
<ul>
<li>被 3 整除 等于 n ：直接计算 3 的 n 次幂</li>
<li>被 3 取余数为1，结果等于 n ：直接计算 3 的 （n-1） 次幂，再乘以4，为什么呢？因为余数是1，我们避免有1，需要借出 3，和 1凑成为 4，4 分段之后的最⼤乘积也是 4（2 * 2）</li>
<li>被 3 取余数为 2，结果等于 n：直接计算 3 的 n 次幂 ，再乘以2</li>
</ul>
<p>也就是说，当n≥5时，优先剪出长度为3的段；剩余4时剪成2×2</p>
<p><strong>为什么选择3？</strong></p>
<ol>
<li><strong>数学证明</strong>：当n ≥ 5时，3(n-3) ≥ 2(n-2) > n</li>
<li><strong>接近自然底数e</strong>：最优分段长度应接近e ≈ 2.718，3是最接近的整数</li>
<li><strong>4的特殊处理</strong>：2×2 > 3×1，所以剩余4时剪成2×2而不是3×1</li>
</ol>
<p>执行过程示例（n=10）：</p>
<pre><code class="language-text">10 ÷ 3 = 3段...剩余1
调整：2段3 → 剩余4 → 剪成2×2
结果：3² × 2² = 9 × 4 = 36
</code></pre>
<p>在计算幂次⽅的时候，为了避免溢出，在每次相乘的时候，都需要除以998244353 ,为了计算快，每次以⾃身相乘的⽅式计算，代码如下：</p>
<pre><code class="language-java">public class Solution {
private static final int MOD = 998244353;
public int cutRope(int n) {
// 特殊情况处理
if (n <= 3) return n - 1;
// 计算可以剪出多少段长度为3的绳子
int countOf3 = n / 3;
// 处理剩余部分：当剩余长度为1时，调整策略
if (n - countOf3 * 3 == 1) {
countOf3--; // 减少一段3，与剩余的1组成4
}
// 计算剩余部分能剪出多少段长度为2的绳子
int countOf2 = (n - countOf3 * 3) / 2;
// 计算结果：3的countOf3次方 × 2的countOf2次方
long result = pow(3, countOf3) * pow(2, countOf2);
return (int) (result % MOD);
}
/**
* 快速幂算法计算a的b次方取模
*/
private long pow(long a, long b) {
long result = 1;
while (b > 0) {
if ((b & 1) == 1) {
result = (result * a) % MOD;
}
a = (a * a) % MOD;
b >>= 1;
}
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(1)，只有常数次操作</li>
<li><strong>空间复杂度</strong>：O(1)，只使用固定变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19558964
頁:
[1]