劍指offer之剪繩子問題

1 問題

給你一根長度為n的繩子，請(qǐng)把繩子剪成m段 (m和n都是整數(shù)，n>1并且m>1)每段繩子的長度記為k[0],k[1],…,k[m].
請(qǐng)問k[0] * k[1] …k[m]可能的最大乘積是多少？
例如，當(dāng)繩子的長度為8時(shí)，我們把它剪成長度分別為2,3,3的三段，此時(shí)得到的最大乘積是18.
 
2 分析

1) 分析邊界值

n和m題目說了，要求大于1，所以繩子長度最少為2，而且每段的長度不能小于1。

當(dāng)n=2的時(shí)候，我們只有一種分割方法，就是中間切斷，變成了1*1 = 1，所以當(dāng)繩子長度為2的時(shí)候，切斷數(shù)長度乘積最大值為1

當(dāng)n=3的時(shí)候，我們有2種分割方法，就是1*1*1 =  1,然后就是1*2 = 2，所以當(dāng)繩子長度為2的時(shí)候，切斷數(shù)長度乘積最大值為2

當(dāng)n=4的時(shí)候，我們有3種分割方法，就是1*1*1*1 =  1,然后就是1*2 *1 = 2，還有2 * 2 = 4，所以當(dāng)繩子長度為2的時(shí)候，切斷數(shù)長度乘積最大值為4；

當(dāng)n=5的時(shí)候，我們有4種分割方法，就是1*1*1*1*1 =  1,然后就是1* 2 *1 * 1 = 2，還有2 * 2 * 1 = 4，還有1 * 3 * 1 = 3，還有2 * 3 = 6;所以當(dāng)繩子長度為2的時(shí)候，切斷數(shù)長度乘積最大值為6；

我們記最大值為f(n)為長度為n繩子剪成若干段的最大乘積，我們可以知道f(n) = max{f(i) * f(n - i)}, i ∈ {1,2...,n - 1},

f(n)的最優(yōu)解對(duì)應(yīng)著f(i)和f(n-i)的最優(yōu)解，假如f(i)不是最優(yōu)解，那么其最優(yōu)解和f(n-i)乘積肯定大于f(n)的最優(yōu)解，然后f(i)又可以看成f(n),大問題包含小問題，并且大問題的最優(yōu)解包含著小問題的最優(yōu)解，所以可以使用動(dòng)態(tài)規(guī)劃求解問題.

    f(4) = max{f(1) * f(3), f(2) * f(2)} = 4;
     
    f(5)= max{f(1) * f(4), f(2) * f(3)} = 6;
     
    ...
     
    f(n) = max{f(1) * f(n -1), ... , f(i) * f(n - i), ... }; 由于具有對(duì)稱性，所以這里的i的范圍是  i ∈ {1, 2..., n / 2};

 
3 代碼實(shí)現(xiàn)

    #include <stdio.h>
    #include <stdlib.h>
     
    int maxCutting(int len)
    {
        if (len <= 1)
        {
            return 0;
        }
        if (len == 2)
        {
            return 1;
        }
        if (len == 3)
        {
            return 2;
        }
        int *data = (int *)malloc(sizeof(int) * len + 1);
        if (data == NULL)
        {
            printf("malloc data fail\n");
            return 0;
        }
        data[0] = 0;
        data[1] = 1;
        data[2] = 2;
        data[3] = 3;
        int max;
        for (int i = 4; i <= len; ++i)
        {
            max = 0;
            for (int j = 1; j <= i / 2; ++j)
            {
                max = data[j] * data[i - j];
                if (data[i] < max)
                {
                    data[i] = max;
                }
            }
            //printf("data[%d] is %d\n", i, data[i]);
        }
        return data[len];
        free(data);
        return 1;
    }
     
    int main(void)
    {
        int result = maxCutting(8);
        if (!result)
        {
            printf("輸入繩子長度不合法或者開辟數(shù)組內(nèi)存失敗\n");
            return -1;
        }
        printf("繩子長度為8的最大切割乘積值為%d", result);
        return 0;
    }

 
4 運(yùn)行結(jié)果

    繩子長度為8的最大切割乘積值為18
     

 
5 總結(jié)

大問題包含小問題，并且大問題的最優(yōu)解包含著小問題的最優(yōu)解，所以可以使用動(dòng)態(tài)規(guī)劃求解問題.動(dòng)態(tài)規(guī)劃我們可以理解成高中數(shù)學(xué)知識(shí)的數(shù)列關(guān)系，既迭代，我們最關(guān)鍵的是找到迭代關(guān)系，如上題f(n) = max(f(i) * f(n -1));
 



 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)