經典題目——剪繩子

剪繩子

引例：給你一根長度為 n 繩子，請把繩子剪成 m 段（m、n 都是整數，2≤n≤58 并且 m≥2）。每段的繩子的長度記為k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘積是多少？例如當繩子的長度是8時，我們把它剪成長度分别為2、3、3的三段，此時得到最大的乘積18。 本題其實是一個數學問題：對于一個整數N，将其分解為m項3、n項2可得到最大乘積。其中（m + n = N, m >= n)。證明如下：

當n<5時，我們會發現，無論怎麼剪切，乘積 <= n，n為4時，product最大為2*2=4；

當n>=5時，可以證明2(n-2)>n并且3(n-3)>n。而且3(n-3)>=2(n-2)。是以我們應該盡可能地多剪長度為3的繩子段。 是以我們可這麼做：先判斷N是否是4的倍數、2的倍數，最後剩下的就全是3的倍數。

class Solution {
public:
    int maxProductAfterCutting(int n) {
        if(n <= 3) return 1*(n-1);
        int res = 1;
        if(n%3 == 1) res *= 4, n -= 4;
        else if(n%3 == 2) res *= 2, n -= 2;
        while(n) res *= 3, n -= 3;
        return res;
    }
};
           

本題還可以利用動态規劃解決，每一步的結果都依賴于上一步的結果。定義函數f(n)表示為把長度為n的繩子剪成若幹段後各段長度乘積的最大值。對于第一刀，我們有n-1種可能的選擇，可推導出f(n)=max{f(i)*f(n-i)};

class Solution {
public:
    int maxProductAfterCutting(int n) {
        if(n <= 3) return 1*(n-1);
        vector<int> vec(n+1);
        vec[0] = 0; vec[1] = 1; vec[2] = 2;vec[3] = 3;
        for(int i = 4; i <= n; i++){//代表和
            int max = 0;
            for(int j = 1; j <= i/2; j++){
                if(vec[j] * vec[i - j] > max){
                    max = vec[j] * vec[i - j];
                }
            }
            vec[i] = max;
        }
        return vec[n];
    }
};