【剑指offer】14、剪绳子

题目

给一根长度为n的绳子，请把绳子剪成m段(m,n都是整数且1)，每段绳子的长度相乘最大乘积是多少？如绳子长度为8，当分别为2，3，3时，此时最大乘积18

思路1

此问题明显包含独立的子问题，用f(n)表示长度为n的绳子剪完后的最大乘积，则可以写出递推公式

f(n) = max{f(n-i) × f(i)}, 0 < i < n

因为自下而上的时间复杂度为O(n), 每次递推时要对i循环O(n) ，所以时间复杂度是O(n²) 

我们对长度为8的绳子进行模拟。

f(4) = f(2) * f(2) = 4;

f(5) = f(2) * f(3) = 6;

f(6) = f(3) * f(3) = 9;

f(7) = f(3) * f(4) = f(2) * f(5) = 12;

f(8) = f(3) * f(5) = 18;

int maxProAfterCutting(int length){if (length < 2) return 0; //题目说大于1，因此这是异常输入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;  //其实是从product[4]开始算，这里是为了计算，当输入0 1 2 3时，前面已经处理int max = 0;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;
}

 

思路2

贪心算法：

当n = 4时，最大乘积就是4.

当n >= 5时，尽可能多剪长度为3的绳子，当剩下为4的时候，就剪成两段2

也就是说，n>=5时，最大乘积都由若干个3，最多两个2构成的

证明很简单：

n >= 5时，3(n-3) >= 2(n-2) > n