经典剪绳子问题

问题描述

《剑指offer》面试题14：剪绳子

给你一根长度为n的绳子，请把绳子剪成m段（n，m都是整数，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);
}
//这个函数适用于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;
}

动态规划

将递归的方式改为从下到上计算，先计算较短绳子的结果并保存在辅助空间中，相比递归可以免去重复计算

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];
}

贪婪算法

当n大于等于5时，我们尽可能多的剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。为什么选2，3为最小的子问题？因为2，3包含于各个问题中，如果再往下剪得化，乘积就会变小。为什么选长度为3？
因为当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的个数
    int cntof3 = n / 3;
    int remainder = n % 3;
    int ans = 1;

    //如果余数为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;
}

有意思的想法

考虑绳子长度可以不为整数

此时变成一个有趣的数学问题，即求 $max(k[1]*k[2]*....*k[m])$
其中k[i]表示第i段绳子的长度。
由算术-几何平均数不等式可知算术平均数总是大于等于几何平均数,即
$A_{n}=\frac{k[1]+k[2]+...+k[n]}{n}\geq \sqrt[n]{k[1]*k[2]*k[3]*...*k[n]}=C_{n}$
当且仅当 $k[1]=k[2]=...=k[n]$ 时取等号。因此每段绳子长度相等时能取得最大值，设将绳子分为m段，每段长度 $n/m$ , $f(m) = (\frac{n}{m})^{m}$
求f(m)的最大值，之后便是有趣的数学计算了。方程两边同时取对数 $ln^{f(m)}=mln^{(\frac{n}{m})}=m(ln^{n}-ln^{m})$
对m求导令导数为零，求极值 $ln^{n}-(ln^{m}+1)=0\Rightarrow m=\frac{n}{e}$
答案中出现了e！！！，只要将一段绳子等长的分为n/e段，每段长度为e，就能让每段长度乘积最大！！多么奇妙！！！易知上面的函数只有一个极大值，也是函数最大值。上面的推导也可以说明贪婪法为什么优先将绳子长度剪为3.