經(jīng)典剪繩子問題

問題描述

《劍指offer》面試題14：剪繩子

給你一根長度為n的繩子，請把繩子剪成m段（n迄靠，m都是整數(shù)妻献，n > 1并且m > 1）晚碾，每段繩子的長度計為k[0],k[1],....,k[m]。請問k[0]k[1],....,*k[m]的最大值是多少扔字？

分析

n是給定的囊嘉，但m沒有給定温技，需要自己選擇將繩子剪成幾段能獲得最大值

遞歸法

考慮將m長的繩子剪成兩段，則最大值為max(1 * (m - 1),2 * (m - 2),3 * (m - 3) .......)
令f(n)為長度為n的繩子能獲得的最大值扭粱，則有遞推公式 f(n) = max(f(i) * f(n - i)) 0 < i < n舵鳞，由此能容易的寫出遞歸方法了

int fun1(int n)
{
    //因為必須分為兩段以上，所以長度小于4和大于4需要分開考慮
    if (n <= 1)
        return 0;
    if (n == 2)
        return 1;
    if (n == 3)
        return 2;
    return recursion(n);
}
//這個函數(shù)適用于n >= 4
int recursion(int n)
{
    //易知邊界條件,長度小于等于4的時候不切
    if (n <= 0)
        return 0;
    if (n <= 4)
        return n;
    int ans = 0;
    for (int i = 1; i <= n / 2; i++)
        ans = max(ans, recursion(i) * recursion(n - i));
    return ans;
}

動態(tài)規(guī)劃

將遞歸的方式改為從下到上計算琢蛤，先計算較短繩子的結(jié)果并保存在輔助空間中蜓堕，相比遞歸可以免去重復(fù)計算

int fun2(int n)
{
    if (n <= 1)
        return 0;
    if (n == 2)
        return 1;
    if (n == 3)
        return 2;
    //dp[i]表示長度為i的繩子能取得的最大乘積
    //dp[i]只使用i>=4的情況
    vector<int> dp(n + 1, 0);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    for (int i = 4; i <= n; i++)
        for (int j = 1; j <= i / 2; j++)
            dp[i] = max(dp[i], dp[j] * dp[i - j]);
    return dp[n];
}

貪婪算法

當(dāng)n大于等于5時，我們盡可能多的剪長度為3的繩子博其；當(dāng)剩下的繩子長度為4時套才，把繩子剪成兩段長度為2的繩子。為什么選2慕淡，3為最小的子問題背伴？因為2，3包含于各個問題中儡率，如果再往下剪得化挂据，乘積就會變小以清。為什么選長度為3儿普？
因為當(dāng)n≥5時，3(n?3)≥2(n?2) 掷倔，3(n-3)≥2(n-2)眉孩。我沒法證明，但是是對的勒葱。

int fun3(int n)
{
    if (n <= 1)
        return 0;
    if (n == 2)
        return 1;
    if (n == 3)
        return 2;
    if (n == 4)
        return 4;
    //3的個數(shù)
    int cntof3 = n / 3;
    int remainder = n % 3;
    int ans = 1;

    //如果余數(shù)為1就少乘一個3 直接乘4
    if (remainder == 1)
    {
        cntof3--;
        ans = 4;
    }
    if (remainder == 2)
        ans = 2;
    for (int i = 0; i < cntof3; i++)
        ans *= 3;
    return ans;
}

有意思的想法

考慮繩子長度可以不為整數(shù)

此時變成一個有趣的數(shù)學(xué)問題浪汪，即求 $max(k[1]*k[2]*....*k[m])$
其中k[i]表示第i段繩子的長度。
由算術(shù)-幾何平均數(shù)不等式可知算術(shù)平均數(shù)總是大于等于幾何平均數(shù),即
$A_{n}=\frac{k[1]+k[2]+...+k[n]}{n}\geq \sqrt[n]{k[1]*k[2]*k[3]*...*k[n]}=C_{n}$
當(dāng)且僅當(dāng) $k[1]=k[2]=...=k[n]$ 時取等號凛虽。因此每段繩子長度相等時能取得最大值死遭，設(shè)將繩子分為m段，每段長度 $n/m$ , $f(m) = (\frac{n}{m})^{m}$
求f(m)的最大值凯旋，之后便是有趣的數(shù)學(xué)計算了呀潭。方程兩邊同時取對數(shù) $ln^{f(m)}=mln^{(\frac{n}{m})}=m(ln^{n}-ln^{m})$
對m求導(dǎo)令導(dǎo)數(shù)為零，求極值 $ln^{n}-(ln^{m}+1)=0\Rightarrow m=\frac{n}{e}$
答案中出現(xiàn)了eＶ练恰Ｄ剖稹！荒椭，只要將一段繩子等長的分為n/e段谐鼎，每段長度為e，就能讓每段長度乘積最大Ｈせ荨狸棍！多么奇妙Ｉ砗Α！草戈！易知上面的函數(shù)只有一個極大值题造，也是函數(shù)最大值。上面的推導(dǎo)也可以說明貪婪法為什么優(yōu)先將繩子長度剪為3.

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者