• 难度：Medium
• 题目链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

题目描述

来源于 https://leetcode-cn.com/

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

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

• 2 <= n <= 58

注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

解法：

设想 n 为一个 m 维立方体各个维度的长度只和，那么本质就是求这个 m 维立方体的最大体积。小学的时候就知道，如果矩形的长宽之和固定，长宽相等时面积最大。如果是 3 维，长宽高之和固定时，构成正方体时体积最大。

因此，我们要把 n 切分成 m 段，让构成的的 m 维立方体的各个维度尽可能相近，就可以让体积最大化。但是究竟要构成多少维的立方体呢？不知道。不过我们可以计算出这个 m 来。

假设切分出来的长度可以是浮点数，那么构成的体积可以表示为：V=(n/m)^m 这里 n 是已知的，可以求出让 V 最大的 m。求个极大值，就可以计算出 m = n / e，这里 e 是自然对数。

由此可以看出切出来的每根绳子长度应该是 e 即 2.718 左右，但是绳子长度只能是整数。因此长度应该在 2 和 3 之间选择。

但是究竟选择 2 还是 3 呢，感觉 3 距离极值点更近，但是也不能确定 3 就是更好的选择。举几个例子，设绳子长度为 12，取长度为 3 和 2 的时候计算出 V 分别为 81 和 64。可见选 3 可以达到最优。

切分存在下面三种情况：

1. 总长度 n 能被 3 整除，那么所有段长度都是 3。
2. n % 3 为 2，此时最后一段绳子长度为 2。
3. n % 3 为 1，此时应该取一段长度为 3 的段，然后分成 2+2。

class Solution {
public:
    int cuttingRope(int n) {
		if(n == 2) return 1;
		if(n == 3) return 2;

		int num_3 = n / 3;
		int num_2 = 0;
		if(n % 3 == 2){
			num_2 = 1;
		}else if(n % 3 == 1){
			num_3 -= 1;
			num_2 = 2;
		}
		return pow(3, num_3) * pow(2, num_2);
    }
};