題目描述

給你⼀根⻓度為n 的繩⼦，請把繩⼦剪成整數⻓的m 段（ m 、n 都是整數， n>1 並 且m>1 ， m<=n ），每段繩⼦的⻓度記為k[1],...,k[m]。請問k[1]x...xk[m] 可能的最⼤乘積是多少？例如，當繩⼦的⻓度是8 時，我們把它剪成⻓度分別為2 、3 、3 的三段，此時得到的最⼤乘積是18`。

輸⼊描述:輸⼊⼀個數n，意義⻅題⾯。（2 <= n <= 60）

返回值描述:輸出答案。

示例1
輸⼊：8
返回值：18

思路及解答

備忘錄

本題的解答思路就是每個⻓度的繩⼦，要麼最⻓的情況是不剪開（⻓度是本身），要麼⻓度是剪開兩段的乘積。因此每個⻓度 length 都需要遍歷兩個相加之後等於 length 的乘積，取最⼤值。

初始化值⻓度為 1 的值為 1 ，從⻓度為 2 開始，每⼀種⻓度都需要遍歷兩個⼦⻓度的乘積。

顯然，為了避免多次重複計算，可以寫個備忘錄

public class Solution {
	public int cutRope(int target) {
		if (target <= 1) {
			return target;
		}
		int[] nums = new int[target + 1];
		nums[1] = 1;
		nums[0] = 1;
		for (int i = 2; i <= target; i++) {
			int max = i;
			for(int j=0;j<=i/2;j++){
				int temp = nums[j] * nums[i-j];
				if(temp > max){
					max = temp;
				}
			}
			nums[i]=max;
		}
		return nums[target];
	}
}

動態規劃

⽤動態規劃的思維來做，假設繩⼦⻓度為 n 的 最⼤的⻓度為 f(n) ，那你説 f(n) 怎麼計算得來呢？

1. f(n) 可能是 n(不切分)
2. 也可能是 f(n-1) 和 f(1) 的乘積
3. 也可能是 f(n-2) 和 f(2) 的乘積
4. ......

那麼也就是想要求 f( n ) 我們必須先把 f(n-1) ， f(n-2) ...之類的前⾯的值先求出來， f(1)=1 這是初始化值。

public class Solution {
	public int cutRope(int target) {
		int[] dp = new int[target + 1];
		dp[1] = 1;
		for (int i = 2; i <= target; i++) {
			for (int j = 1; j < i; j++) {
				dp[i] = Math.max(dp[i], (Math.max(j, dp[j])) * (Math.max(i - j, dp[i - j])));
			}
		}
		return dp[target];
	}
}

• 時間複雜度：O(n²)，外層循環n-3次，內層循環i/2次
• 空間複雜度：O(n)，需要dp數組存儲中間結果

貪心算法（最優解）

基於數學推導的貪心策略，優先剪出長度為3的段。當n≥5時，優先剪出長度為3的段；剩餘4時剪成2×2

為什麼選擇3？

1. 數學證明：當n ≥ 5時，3(n-3) ≥ 2(n-2) > n
2. 接近自然底數e：最優分段長度應接近e ≈ 2.718，3是最接近的整數
3. 4的特殊處理：2×2 > 3×1，所以剩餘4時剪成2×2而不是3×1

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));
    }
}

• 時間複雜度：O(1)，只有常數次操作
• 空間複雜度：O(1)，只使用固定變量

數學公式法（理論最優）

根據n除以3的餘數直接套用公式

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;
        }
    }
}

• 時間複雜度：O(1)
• 空間複雜度：O(1)