剪绳子

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

AC代码

class Solution {
public:
    int cutRope(int number) {
        if (number == 2) {
            return 1;
        }
        if (number == 3) {
            return 2;
        }
        switch (number % 3){
            case 0:
                return pow(3, number / 3);
            case 1:
                return 4 * pow(3, number / 3 - 1);
            case 2:
                return 2 * pow(3, number / 3);
        }
    }
};

知识点

• 如果我们给一个长度n,规定分成x份(x为整数),那么问如何分,使得分下来的数乘积最大?

  均分.

• 如果我们给一个长度n,不规定份数,问如何分,乘积最大

  每一段长度越接近e越好.

假设每一段长度为x,乘积为f(x)
f(x) = x ^ (n/x);

• f'(x)

  
  

• f(x)的图像

  
  

以2.8为例
分两份 1.4 * 1.4 = 1.96
分2.8份(假设可以为小数) 1 ^ 2.8 = 1;
分(2.8/2.7) 份 2.7 ^ (2.8/2.7) = 2.8011...

所以倘若要分成整数份且长度为整数,应保证3尽可能多.
当然,因为4分成2 * 2比1 * 3更大,所以要做余数讨论.