這道題的一般解法是動態規劃，優化時可以嘗試找規律。

原題

給你一根長度爲 n 的繩子，請把繩子剪成整數長度的 m 段（m、n都是整數，n>1並且m>1），每段繩子的長度記爲 k[0],k[1]...k[m] 。請問  k[0]*k[1]*...*k[m] 可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分別爲2、3、3的三段，此時得到的最大乘積是18。

示例 1：

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1

示例 2:

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

  • 2 <= n <= 58

原題url：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

解題

動態規劃 DP

我們想想，本題要求是計算 n 被分成 m 份後，相乘最大的結果，這比較明顯可以看出是需要求一定要求下的最優解，那麼如果能求出局部最優解的話，也能求出方便求出最終最優解。講白了，就是一個個試，但需要保證需要將所有情況都計算過，且不要重複計算。

那這就要利用動態規劃的思想了，從初始情況開始，一步步遞推。假設繩子長度爲 x ，其最大乘積爲 f(x)，則有：

f(2) = 1; (1 * 1)
f(3) = 2; (1 * 2)
f(4) = 4; (2 * 2)
f(5) = 6; (3 * 2)
f(6) = 9; (3 * 3)
f(7) = 12; (3 * 2 * 2 = 3 * f(4))
f(8) = 18; (3 * 3 * 2 = f(6) * 2 = 3 * f(5))

自己先試着寫出初始的情況，然後從中找出規律：

  1. 長度1、2、3，並沒有繼續分隔的必要，其作爲整體，直接參與計算應該就是最大的數字了。

  2. 長度4，分隔成2、2是比較合理的。

  3. 當長度越長，被分隔成的數量越多時，其實可以想象成將其中多段合併成1段，最後都是可以當做分隔成2段來計算的。

因此，根據上面總結出來的規律，我們應該是需要從小開始計算，並將中間結果保留，因此可以用一個數組進行存儲。

我們來看看代碼：

class Solution {
    public int cuttingRope(int n) {
        if (n == 2) {
            return 1;
        }
        // 記錄計算結果，第2位代表長度爲2的繩子，其最大乘積
        int[] result = new int[n + 1];
        result[1] = 1;
        result[2] = 1;
        for (int i = 3; i <= n; i++) {
            // 默認初始值就是剪成兩段：1 和 i-1，所以最大乘積是 i-1
            result[i] = i - 1;
            for (int j = 1; j <= i / 2; j++) {
                int x = Math.max(result[i - j], i - j);
                int y = Math.max(result[j], j);
                result[i] = Math.max(x * y, result[i]);
            }
        }
        return result[n];
    }
}

提交OK。

數學推導的極致優化

這個解法，我也是看了別人的解析才知道的，通過代碼提交發現結論確實是正確的，但其中的推導過程我也沒有看懂，看看原文：

接下來我們看看代碼：

class Solution {
    public int cuttingRope(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        // 可以被3分成幾段
        int count = n / 3;
        // 剩餘的數字
        int remain = n % 3;
        // 如果沒有剩餘的
        if (remain == 0) {
            // 直接計算當前的值
            return (int) Math.pow(3, count);
        }
        // 如果剩1，則和原本的一個3，重新拆分成2和2，因爲2 * 2 > 3 * 1
        if (remain == 1) {
            return (int) Math.pow(3, count - 1) * 2 * 2;
        }
        // 如果剩2，則正常乘
        return (int) Math.pow(3, count) * 2;
    }
}

提交OK。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題的一般解法是動態規劃，優化時可以嘗試找規律，數學推導出其中當然是最快的，但這需要一定的功底。

有興趣的話可以訪問我的博客或者關注我的公衆號，說不定會有意外的驚喜。

https://death00.github.io/

公衆號：健程之道

點擊此處留言

相關文章