# 劍指 Offer 14- I. 剪繩子

目錄

• 1.題目
• 2.自我思路及實作
• 3.總結思路及實作
• • 1.數學推導
  • 2.動态規劃
  • 3.優化的動态規劃
  • 4.查表
• 4.總結
• 5.大數取餘
• • 1.循環求餘
  • 2.快速幂求餘

1.題目

劍指 Offer 14- I. 剪繩子
給你一根長度為 n 的繩子，請把繩子剪成整數長度的 m 段（m、n都是整數，n>1并且m>1），每段繩子的長度記為 k[0],k[1]...k[m-1] 。請問 k[0]*k[1]*...*k[m-1] 可能的最大乘積是多少？例如，當繩子的長度是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
           

2.自我思路及實作

相同的數相乘最大，但分為多少段是最合适的這個無法确定。

3.總結思路及實作

1.數學推導

時間：1，求整、求餘、次方運算

求整和求餘：不超過機器數的整數可看作O(1)

次方：浮點取幂為O(1)

空間：1

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3)
            return n - 1;
        int a = n / 3;
        int b = n % 3;

        //可以被3整除，直接将所有3相乘
        if(b == 0)
            return (int)Math.pow(3, a);

        //餘1，将一組3 * 1改為 2 * 2
        else if(b == 1)
            return (int)Math.pow(3, a - 1) * 2 * 2;

        //餘2，直接乘上最後的2
        else
            return (int)Math.pow(3, a) * 2; 
        
    }
}
           

2.動态規劃

設dp[i]代表i被拆分後的整數乘積最大值，i被拆分出j後，剩下的值為（i- j）,i-j有兩種處理方式

1.不再拆分，那麼此時整數乘積為(i - j ) * j

2.将i- j繼續拆分，此時整數乘積為 dp[i - j] * j

dp[i] = 上述二者之間的最大值

j 的範圍為1≤j＜i

時間：n2，雙循環

空間：n

class Solution {
    public int integerBreak(int n) {
        //dp[i]是i被拆分後的整數的最大乘積
        int[] dp = new int[n + 1];

        int curMax = 0;
        for(int i = 2; i <= n ; i++)
        {
            for(int j = 1; j < i; j++)
            {
                curMax = Math.max(curMax, Math.max((i - j ) * j, dp[i - j] * j));
            }
            dp[i] = curMax;

        }
        return dp[n];

    }
}
           

3.優化的動态規劃

當i 大于3時，隻考慮j為2或3的情況

時間：N

空間：N

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3)
            return n - 1;

        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++)
        {
            dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
        }
        return dp[n];   
    }
}
           

4.查表

滿足了全部的使用情況

class Solution {
    public int cuttingRope(int n) {
        int[] res = {0, 0, 1, 2, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324, 486, 729, 972, 1458, 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244, 39366, 59049, 78732, 118098, 177147, 236196, 354294, 531441, 708588, 1062882, 1594323, 2125764, 3188646, 4782969, 6377292, 9565938, 14348907, 19131876, 28697814, 43046721, 57395628, 86093442, 129140163, 172186884, 258280326, 387420489, 516560652, 774840978, 1162261467, 1549681956};
        return res[n];
    }
}
           

4.總結

• 3為最優解，其次為2

5.大數取餘

問題在于當我們進行幂運算時，每次乘3的結果都可能超過1e9+7，是以每一步都需要取餘

1.循環求餘

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3)
            return n - 1;
        long res = 1;

        while(n > 4)
        {
            res = res * 3 % 1000000007;
            n -= 3;
        }
        //n可能為2，3，4
        return (int)(res * n % 1000000007);

    }
}
           

時間：N，循環的時間複雜度

空間：1

2.快速幂求餘

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3)
            return n - 1;
        int b = n % 3;
        int p = 1000000007;
        long res = 1;
        long x = 3;

        for(int a = n / 3 - 1; a > 0; a /= 2)
        {
            if(a % 2 == 1)//奇數
                res = (res * x) % p;
            x = (x * x) % p; 

        }

        if(b == 0)
            return (int)(res * 3 % p);
        if(b == 1)
            return (int)(res * 4 % p);
        return (int)(res * 6 % p);

    }
}