面试题14:剪绳子

题目

给你一根长度为n的绳子，请把绳子剪成m段(m,n都是整数，n>1且m>1)。每段绳子的长度记为k[0],k[1],.....,k[m]。请问k[0]k[1]....*k[m]可能的最大乘积是多少?
举例:当绳子的长度是8时，先把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18.

解题思路

• 动态规划
  尝试把大问题分解成小问题，分解后的每个小问题也存在最优解。如果把小问题的最优解组合起来能够得到整个问题的最优解，那么可以应用动态规划解决这个问题。

1. 把长度为n的绳子剪成若干段后得到的乘积最大值定义为函数f(n)。假设第一刀剪在长度为i(0<i<n)的位置，于是绳子剪成长度分别为i和n-i的两段。要想得到整个问题的最优解f(n)，那么要同样用最优化的方法把长度为i和n-i的两段分别剪成若干段。
2. 采用从下往上的顺序计算小问题的最优解并存储下来，再依次为基础求取大问题的最优解。

• 贪婪算法
  应用贪婪算法解决问题时，每一步都可以做出一个贪婪选择，基于这个选择，确定能够得到最优解。
  当绳子的长度大于5时，每次都剪出一段长度为3的绳子。

代码

• 动态规划
• 细节
  自上而下分析问题，自下而上解决问题。

1. 先计算前三个小问题的最优解并存储在products数组中
2. 从长度为4的绳子开始分析每一种可能性，并取最大值。

class Solution{
  public:
    int maxProductAfterCutting(int length)
    {
        if(length < 2)  return 0;
        if(length == 2) return 1;
        if(length == 3) return 2;

        int *products = new int[length+1];
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;

        int max;
        for(int i = 4;i <= length; i++)
        {
            max = 0;
            for(int j = 1;j<=i/2;j++)
            {
                int product = products[j]*products[i-j];
                if(max < product)
                {
                    max = product;
                }
            }
            products[i] = max;
        }

        max = products[length];
        delete[] products;

        return max;
    }
};

• 贪婪算法

class Solution{
  public:
    int maxProductAfterCutting2(int length)
    {
        if(length < 2)  return 0;
        if(length == 2) return 1;
        if(length == 3) return 2;
        //尽可能多地减去长度为3的绳子
        int timesOf3 = length / 3;
        //若绳子最后剩下的长度为4时，不用再减去长度为3的绳子段
        //此时更好的方法是把绳子剪成长度为2的两段，因为2*2 > 3*1
        if(length - timesOf3/3 == 1)
        {
            timesOf3 -= 1;
        }

        int timesOf2 = (length - timesOf3 * 3) / 2;
        return (int)(pow(3,timesOf3))*(int)(pow(2,timesOf2));
    }
};

完整代码见Github