剑指offer-67、剪绳⼦
<h2 id="题目描述">题目描述</h2><p>给你⼀根⻓度为n 的绳⼦，请把绳⼦剪成整数⻓的m 段（ m 、n 都是整数， n>1 并 且m>1 ， m<=n ），每段绳⼦的⻓度记为k,...,k。请问kx...xk 可能的最⼤乘积是多少？例如，当绳⼦的⻓度是8 时，我们把它剪成⻓度分别为2 、3 、3 的三段，此时得到的最⼤乘积是18`。</p>
<p>输⼊描述:输⼊⼀个数n，意义⻅题⾯。（2 <= n <= 60）</p>
<p>返回值描述:输出答案。</p>
<p>示例1<br>
输⼊：8<br>
返回值：18</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="备忘录">备忘录</h3>
<p>本题的解答思路就是每个⻓度的绳⼦，要么最⻓的情况是不剪开（⻓度是本身），要么⻓度是剪开两段的乘积。因此每个⻓度 length 都需要遍历两个相加之后等于 length 的乘积，取最⼤值。</p>
<p>初始化值⻓度为 1 的值为 1 ，从⻓度为 2 开始，每⼀种⻓度都需要遍历两个⼦⻓度的乘积。</p>
<p>显然，为了避免多次重复计算，可以写个备忘录</p>
<pre><code class="language-java">public class Solution {
public int cutRope(int target) {
if (target <= 1) {
return target;
}
int[] nums = new int;
nums = 1;
nums = 1;
for (int i = 2; i <= target; i++) {
int max = i;
for(int j=0;j<=i/2;j++){
int temp = nums * nums;
if(temp > max){
max = temp;
}
}
nums=max;
}
return nums;
}
}
</code></pre>
<h3 id="动态规划">动态规划</h3>
<p>⽤动态规划的思维来做，假设绳⼦⻓度为 n 的 最⼤的⻓度为 f(n) ，那你说 f(n) 怎么计算得来呢？</p>
<ol>
<li>f(n) 可能是 n(不切分)</li>
<li>也可能是 f(n-1) 和 f(1) 的乘积</li>
<li>也可能是 f(n-2) 和 f(2) 的乘积</li>
<li>......</li>
</ol>
<p>那么也就是想要求 f( n ) 我们必须先把 f(n-1) ， f(n-2) ...之类的前⾯的值先求出来， f(1)=1 这是初始化值。</p>
<pre><code class="language-java">public class Solution {
public int cutRope(int target) {
int[] dp = new int;
dp = 1;
for (int i = 2; i <= target; i++) {
for (int j = 1; j < i; j++) {
dp = Math.max(dp, (Math.max(j, dp)) * (Math.max(i - j, dp)));
}
}
return 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>基于数学推导的贪心策略，优先剪出长度为3的段。当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>
<pre><code class="language-java">public class Solution {
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次方
return (int)(Math.pow(3, countOf3)) * (int)(Math.pow(2, countOf2));
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(1)，只有常数次操作</li>
<li><strong>空间复杂度</strong>：O(1)，只使用固定变量</li>
</ul>
<h3 id="数学公式法理论最优">数学公式法（理论最优）</h3>
<p>根据n除以3的余数直接套用公式</p>
<pre><code class="language-java">public class Solution {
public int cutRope(int n) {
if (n <= 3) return n - 1;
int countOf3 = n / 3;
int remainder = n % 3;
// 根据余数直接返回结果
if (remainder == 0) {
return (int) Math.pow(3, countOf3);
} else if (remainder == 1) {
return (int) Math.pow(3, countOf3 - 1) * 4;
} else { // remainder == 2
return (int) Math.pow(3, countOf3) * 2;
}
}
}
</code></pre>
<ul>
<li>时间复杂度：O(1)</li>
<li>空间复杂度：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/19495627
頁:
[1]