剑指offer小解析——14_I_剪绳子
1.题目描述
难度中等112
给你一根长度为 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
2.动态规划
2.1 正常人的思维
//time: 38.74%
//memory: 77.31%
public static int cuttingRope(int n) {
if (n < 2) {
return 0;
}
if (n == 2) {
return 1;
}
int[] res = new int[n + 1];
res[1] = 0;
res[2] = 1;
int max = 0;
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= i / 2; j++) {
int temp = (Math.max(j, res[i]) * Math.max((i - j), res[i - j]));
if (temp > max) {
max = temp;
}
}
res[i] = max;
}
return res[n];
}
这里我们可以想一想曾经做过的斐波那契数列，对于本题来说，我们提供两个初始值，绳长为1（或者为0）时我们返回0，因为1已经是最小单位了，剪不了了；绳长为2时我们返回1，即剪成1米和1米的两段。
如果绳长大于2呢？我们可以设置一个数组来存储每个长度对应的最优结果。我们设这个数组为res，res的下标代表绳子长度，即res[1]代表绳长为1米，res[2]代表绳长为2米……，那么我们初始化res[1] = 0， res[2] = 1。
做完初始化工作后，我们就要开始利用已有的结果计算未知的结果。我们首先写一个循环，从3开始，到绳长为n时结束，这个循环代表了绳子的长度。比如i = 4，说明我们正在计算绳长为4米时候的最优解。
然后我们进行剪绳，本来我们可以剪的长度是从1米到i - 1米，但举个例子来说，2 + 4 = 6，可4 + 2也等于6，这样就重复了，我们只需要剪到中间就行，不需要再往右了。
如果绳长为3米，我们的最优剪法应该是剪成1米和2米，结果为2，我们想当然地使用res[j] * res[i - j] （j就是你剪断的长度，i -j就是剩下的长度）= res[2] * res[1] = ……欸，等等，res[2] = 1，res[1] = 0，这俩乘积是0啊！
这就需要你仔细想一想，无论是res[2]还是res[1]，都是他们作为题目输入的长度时，必须剪绳子获得的最优解，但是如果他们作为计算的中间量的时候，就比如我们输入3，剪断成2和1，你还必须剪那个2米的绳子吗？不需要，因为他是中间量，我们没必要非得剪断他，很明显，2米绳子的本身长度大于他作为输入时的最优解，所以我们选择使用Math.max方法来获得2米绳子的长度及其最优解之间的最大值即可。
然后就简单了，我们定义一个max量，记录乘积的最大值。每次内循环结束这个max值归零或者不归零都行，反正他都是递增的，每次循环都一定会产生一个值把他覆盖掉，无所谓。
但是这个解法，耗时，时间上只能达到38%，还不够好，问题出在哪里呢？
2.2 很多人都会写但没多少人证明过的一种方式
public int cuttingRope(int n) {
if (n < 2) {
return 0;
}
if (n == 2) {
return 1;
}
if (n == 3) {
return 2;
}
int[] res = new int[n + 1];
res[1] = 0;
res[2] = 2;
res[3] = 3;
int max = 0;
for (int i = 4; i <= n; i++) {
for (int j = 1; j <= i / 2; j++) {
int temp = res[j] * res[i - j];
if (temp > max) {
max = temp;
}
}
res[i] = max;
}
return res[n];
}
我们先带着上面的疑问，看完上面的代码，觉得这个跟之前的思路也差不多，稍微看看好像能看懂，但是，又总觉得哪里不对劲？
为什么是4，我的循环为什么要从4开始？不是从5或者6或者100？res[2]是啥？res数组不应该记录的最优解吗？如果res[2]代表的是2米长的绳子的最优解，不应该是1吗？咋res[1]、res[2]、res[3]的值都等于他们自身的长度了？
这个问题的核心原因，也是2.1小节耗时过多的原因——判断一段绳子的最优解是否比它的本身长？
换个说法，比如我有一个3米长的绳子，如果他作为题目本身，让你剪一个3米长的绳子，你知道最优解是1* 2 = 2；但是如果我的绳子长4米呢？当你把绳子剪成3米和1米的时候，你还会继续剪那个3米长的绳子吗？你不会，因为如果继续剪3米的那段，你就把3 * 1 = 3变成了1 * 2 * 1 = 2，反而减小了。所以如果剪断的过程中出现3米的子绳段，我们选择不剪，直接保留，因为他的最优解小于他本身的长度。这也是为什么我们在2.1小节，每次都要使用Math.max方法。
但是，我们真的每次都需要Math.max吗？比如4，我们知道他的最优解是剪成2 、 2的两段，结果是4，等于绳长；5可以分成2和3，结果是6，比5还大；6可以分成2和4，结果是8；7可以分成3和4，结果是12……wait a minute，好像，从4开始，他们的最优解都大于或者等于绳子的长度。那么我们是否可以这样，如果输入的n是0到3，我们直接返回最优解；但是如果n大于3，那么我们设作为子段的0、1、2、3的**“最优解”**分别都是他们自身的长度。然后每次循环计算的时候我们就可以直接使用int temp = res[j] * res[i - j];了，这样岂不妙哉？
But，你这么做的前提是啥？前提是知道上面的猜想从4开始，他们的最优解都大于或者等于绳子的长度是正确的，接下来就是证明。
（警告🔥，以下涉及数学知识，而且我高数已经快忘完了，写的跟喝醉了似的，你看不懂不要怀疑自己，绝对是我写的不够清楚明白）
首先我们假设一个数字n( n ∈ Z + n \in Z_{}^{+} n∈Z+)，并且设他的一个加数为x，我们要找到一个最小值，从这个值开始，所有的数一定存在一组加数，使得这两个加数的成绩大于等于这个数本身。用符号描述就是
∀ m ∈ Z + , 如 果 m ≥ n ( n ∈ Z + ) , 则 ∃ x < m , 使 得 ( m − x ) × x ≥ m 。 求 n 。 \forall m \in Z_{}^{+}, 如果m \geq n(n \in Z_{}^+),则\exists x < m,使得(m - x)\times x \geq m。求n。 ∀m∈Z+,如果m≥n(n∈Z+),则∃x<m,使得(m−x)×x≥m。求n。
那么我们需要利用 ( n − x ) × x ≥ n (n - x)\times x \geq n (n−x)×x≥n来求得n的最小值（很明显x一定是大于1的，也就是x≥2，因为如果x=1，结果只能是n-1，不可能等于或者大于n的）
通过化简，我们获得了 x 2 x − 1 ≤ n ( x ≥ 2 ) \frac{x^{2}}{x - 1} \leq n (x \geq 2) x−1x2≤n(x≥2) ，我们现在只需要求得 x 2 x − 1 \frac{x^{2}}{x - 1} x−1x2 的最小值。
对 x 2 x − 1 \frac{x^{2}}{x - 1} x−1x2 进行变形，获得 ( x − 1 ) 2 + 2 x − 1 x − 1 \frac{(x - 1)^2 + 2x - 1}{x - 1} x−1(x−1)2+2x−1 ，即 x − 1 + 2 x − 1 x − 1 x - 1 + \frac{2x - 1}{x - 1} x−1+x−12x−1
继续变形化简，获得 x + 1 + 1 x − 1 x + 1 + \frac{1}{x - 1} x+1+x−11
求导获得 1 − 1 ( x − 1 ) 2 = x ( x − 2 ) ( x − 1 ) 2 ( x ≥ 2 ) 1 - \frac{1}{(x - 1)^2} = \frac{x(x-2)}{(x-1)^2}(x\geq 2) 1−(x−1)21=(x−1)2x(x−2)(x≥2)
很明显，在x≥2的区间范围内， x 2 x − 1 \frac{x^{2}}{x - 1} x−1x2 的导数始终大于等于0，即它始终是增函数，最小值即为x=2时。我们带入得到4，也就是说，从4开始，n一定存在两个加数的乘积大于等于n。那么放到我们的题目就是从，每个子段，只要他的长度大于4，他的最优解一定大于他自身的长度。
上面如果我讲的还不够清楚，没关系，你只需要知道我们的思路应该是这样
- 如果绳子的长度为0、1、2、3，你就直接返回对应的最优解即可，即0、0、1、2；
- 如果绳子的长度大于等于4，我们定义res数组，注意，res的下标就是绳子的长度。那么现在res[1]，res[2]，res[3]代表的是长度为1、2、3的**子段（注意，他们是作为子段，就是过程中被剪出来的绳子）**能提供的最大长度，我们分别设为他们各自的长度（通过上面的证明我们已经知道，只有大于4的线段才会出现加数乘积大于本身的情况，所以1、2、3这些段如果是作为中间量出现的话，就没必要继续剪下去了）。
别的我就不多说了，只要理解了上面的，这个代码本身没有难度，10分钟就能完整地背下来。
3.贪婪算法
在说这个算法之前，我们可以看看如果我们输入n = 10，利用上面的动态规划算***怎么运行
运行到10，可以分成2和8，8又可以分成2和6，6又可以分成3和3，最后的结果也就是2 * 2 * 3 * 3 = 36
我们发现了，在剪绳子宇宙的尽头是铁岭……不对，
我们发现，宇宙的尽头是2和3，你无论是什么数我最后都能给你分成2和3，而且当n ≥5的时候，你证明一下，
3(n - 3) ≥ 2(n - 2)
这说明当n ≥5的时候，应该尽量剪出来3米的绳子。而当长度为4的时候，2 * 2 > 1 * 3，这时候我们就要收手，要剪出来两段2米的。
那么我们用n / 3 获得可以分成的3米的数量numberOf3，这时候余数可能为1或者2，如果余数是1，我们就让numberOf3-1，拿出一个3米的子段跟1米合并，成为1个4米的子段，这样效果更好。
如果余数是2，那就让它2着，不用管
然后我们通过(n - numberOf3 * 3) / 2来获得2米子段是数量numberOf2，最后利用Math.pow(3, numberOf3)*Math.pow(2, numberOf2)来获得结果。
public int cuttingRope(int n) {
if (n < 2) {
return 0;
}
if (n == 2) {
return 1;
}
if (n == 3) {
return 2;
}
int numberOf3 = n / 3;
if (n - 3 * numberOf3 == 1) {
numberOf3--;
}
int numberOf2 = (n - numberOf3 * 3) / 2;
return (int)(Math.pow(3, numberOf3) * Math.pow(2, numberOf2));
}
4.最后叨逼两句
说实话，什么动态规划，贪婪，我还真不知道怎么就动态了，怎么就贪婪了，之前做题的时候看到一个老哥的话，不要死记模板，见到一个题，知道大致的方向，见招拆招即可，没必要非得分那么细，这个是干嘛的，那个得用哪个套路，反正我不会（主要还是刷的少，估计以后刷多了也就很自然地写出来了）。
京公网安备 11010502036488号