給你一根長度為 n 的繩子，請(qǐng)把繩子剪成 m 段（m挪丢、n 都是整數(shù)蹂风，并且）。每段的繩子的長度記為乾蓬、惠啄、……、。可能的最大乘積是多少礁阁？例如當(dāng)繩子的長度是 8 時(shí)巧号，我們把它剪成長度分別為 2、3姥闭、3 的三段丹鸿，此時(shí)得到最大的乘積 18。

解析：該題可以用動(dòng)態(tài)規(guī)劃的思路解棚品，也可以用貪心算法的思路解靠欢。
動(dòng)態(tài)規(guī)劃的話，首先看滿不滿足這兩個(gè)經(jīng)典的條件：大問題可以分解為若干個(gè)小的子問題铜跑，而且子問題需要大量的重復(fù)計(jì)算门怪。這兩個(gè)條件在這里都是滿足的：例如繩子的長度是 12 的時(shí)候，一刀切下去變成 2 和 10锅纺，10 就成了一個(gè)子問題掷空。10 還需要一刀切下去變成 2 和 8，這樣 2 就重復(fù)了一次囤锉。雖說把 12 切成 2 和 10 不一定是最好的方案坦弟，但是我的目的在于證明子問題是有重復(fù)情況發(fā)生的。這個(gè)時(shí)候可以把子問題得到的結(jié)果提前記錄下來官地，從而盡量避免無意義的重復(fù)酿傍，寫法也就不是函數(shù)遞歸了，能夠獲得比較好的算法驱入。在確定可以使用動(dòng)態(tài)規(guī)劃的時(shí)候赤炒，我們需要明確自己的目的：我們要找到最優(yōu)的子問題劃分。把 12 切成 2 和 10 好呢亏较，還是切成 3 和 9 好呢莺褒？顯然，宴杀，所以選擇 3 和 9 比 2 和 10 要好癣朗。但是 3 和 9 就一定是最好的嗎？旺罢，那么 4 和 8 就一定最好嗎？你會(huì)發(fā)現(xiàn)绢记，從上到下的分析扁达，并不容易得到正確答案。那么我們應(yīng)該換一種思路蠢熄，從下到上的分析：

• 假設(shè)繩子總共有 2 厘米長跪解，由于必須剪一刀，乘積是 1签孔。
• 假設(shè)繩子總共有 3 厘米長叉讥，那么乘積是 2窘行。
• 假設(shè)繩子總共有 4 厘米長，剪成 2 和 2 要比 1 和 3 強(qiáng)图仓，乘積是 4罐盔。注意，我們可以只剪一刀救崔，這樣子條件已經(jīng)滿足了惶看，剪出來的 3 不需要再剪一刀了，因?yàn)樵偌粢坏斗炊尦朔e變小了六孵。
• 假設(shè)繩子總共有 5 厘米長纬黎，剪成 2 和 3 要比 1 和 4 強(qiáng)。同樣劫窒，剪出來的 3 和 4 不需要再剪一刀了本今，因?yàn)樵偌粢坏斗炊尦朔e變小了。
• 假設(shè)繩子總共有 6 厘米長主巍，剪成 3 和 3 要比 2 和 4 強(qiáng)诈泼。

分析到這里的時(shí)候，我們其實(shí)已經(jīng)有一些子問題的結(jié)果了煤禽。剪出來的繩子片段：

• 長度為 1 的時(shí)候铐达，它最高能貢獻(xiàn)的乘積因子是 1；
• 長度為 2 的時(shí)候檬果，它最高能貢獻(xiàn)的乘積因子是 2瓮孙；
• 長度為 3 的時(shí)候，它最高能貢獻(xiàn)的乘積因子是 3选脊，因?yàn)橹耙呀?jīng)剪過一刀了杭抠，所以不需要把 3 再剪一次；
• 長度為 4 的時(shí)候恳啥，它最高能貢獻(xiàn)的乘積因子是 4偏灿，這個(gè)時(shí)候多剪一刀與不剪是沒區(qū)別的；
• 長度為 5 的時(shí)候钝的，它最高能貢獻(xiàn)的乘積因子是 6翁垂，如果這個(gè)片段不剪的話能貢獻(xiàn) 5，剪了的話能貢獻(xiàn) 硝桩，當(dāng)然選擇再剪一刀沿猜；
• 長度為 6 的時(shí)候，它最高能貢獻(xiàn)的乘積因子是 9碗脊，不剪的話能貢獻(xiàn) 6啼肩，剪了的話能貢獻(xiàn) ，當(dāng)然選擇再剪一刀；
• ……

發(fā)現(xiàn)沒有祈坠，上面的剩余長度為 4 的問題害碾，可以理解成兩個(gè)剩余長度為 2 的乘積；剩余長度為 5 的問題赦拘，可以理解為兩個(gè)剩余長度為 2 和 3 的乘積慌随；剩余長度為 6 的問題，可以理解為兩個(gè)剩余長度為 3 的乘積……如果用函數(shù)的思想另绩，用代表繩子剩余長度為 n 的時(shí)候能夠提供的最大貢獻(xiàn)儒陨，那么，笋籽，蹦漠，，车海，……

我們在確定笛园、、的值的時(shí)候侍芝，是通過比較兩個(gè)子問題乘積的更大值來得到的研铆。例如在判定的時(shí)候，州叠，也可以是棵红，這兩種情況中前者更大，所以選擇前者的方案咧栗。更一般的逆甜，我們考慮，我們比較的過程是，，忌锯，，……胁黑，這么多結(jié)果中最大的那一個(gè)。在剛剛的考慮過程中，、這些值在之前的計(jì)算已經(jīng)記錄了結(jié)果御毅，所以我們直接用就好。

分析到這一步了平斩，你是不是已經(jīng)很清楚動(dòng)態(tài)規(guī)劃的代碼該怎么寫了亚享？

// ====================動(dòng)態(tài)規(guī)劃====================
int maxProductAfterCutting_solution1(int length)
{
    if (length < 2) return 0;
    else if (length == 2) return 1;
    else if (length == 3) return 2;
    else if (length >= 4)
    {
        int product[length+1];
        product[0] = 0; //這個(gè)其實(shí)寫不寫都行，后面的代碼也用不到這個(gè)
        product[1] = 1; //這個(gè)也用不到
        product[2] = 2; //這里的 2 指的是剩下了一段長度為 2 的繩子绘面，可以不剪
        product[3] = 3; //這里的 3 指的是剩下了一段長度為 3 的繩子，可以不剪

        int max = 0;
        for (int i=4; i<=length; ++i)
        {
            max = 0;
            for (int j=2; j<=i/2; ++j) //從 2 開始比較
            {
                if (max < product[j]*product[i-j])
                    max = product[j]*product[i-j]; //比較出最大的那個(gè)情況
            }
            product[i] = max; //記錄下來
        }
        return product[length]; //這個(gè)時(shí)候從 0 到 n 的最優(yōu)情況都記錄下來了
    }
    return 0;
}

下一個(gè)思路是貪心算法。在使用貪心算法的時(shí)候揭璃，我們同樣需要提供一些數(shù)學(xué)證明晚凿，來證明可以用貪心的思路解題。同樣的瘦馍，

• 假設(shè)繩子總共有 2 厘米長歼秽，由于必須剪一刀，乘積是 1情组。
• 假設(shè)繩子總共有 3 厘米長燥筷，那么乘積是 2。
• 假設(shè)繩子總共有 4 厘米長院崇，剪成 2 和 2 要比 1 和 3 強(qiáng)肆氓，乘積是 4。
• 假設(shè)繩子長度大于 5 厘米底瓣，即 谢揪，我們可以證明。因此切比不切強(qiáng)捐凭，而且切成 3 的情況比切成 2 的情況貢獻(xiàn)的乘積多拨扶，我們應(yīng)該盡量多切成 3 的片段。

因此茁肠，思路就很簡單了：如果把繩子盡可能多的切成若干個(gè) 3 的片段患民，剩下來的長度可能是 1、2垦梆，如果少切一刀的話匹颤，也會(huì)剩下 4、5奶赔、6惋嚎。為什么考慮少切一刀的情況呢？我們來看一下：

• 如果切到最后剩下了長度為 6 的片段站刑，再切出來一段 3另伍，剩余 3，能多乘 9绞旅，那就切摆尝；
• 如果切到最后剩下了長度為 5 的片段，再切出來一段3因悲，剩余 2堕汞，能多乘 6，那就切晃琳；
• 如果切到最后剩下了長度為 4 的片段讯检，再切出來一段3琐鲁，剩余 1，能多乘 3人灼；但是如果不切的話围段，能多乘 4！

那么這個(gè)剩余長度是 4 的情況就是特殊情況：如果剩余長度為 4投放，那么選擇不切奈泪，而不是切成 1 和 3。到這里灸芳，算法就能寫出來了：

// ====================貪心算法====================
int maxProductAfterCutting_solution2(int length)
{
    if (length < 2) return 0;
    else if (length == 2) return 1;
    else if (length == 3) return 2;
    else
    {
        int piecesOfThree = length/3;
        //pow 函數(shù)的結(jié)果是 double 類型涝桅，所以使用類型轉(zhuǎn)換：
        int productOfThrees = static_cast<int>(pow(3, piecesOfThree));
        if (length%3==0) return productOfThrees;
        else if (length%3==2) return 2*productOfThrees;
        else return productOfThrees/3*4;
    }
}