题解 | #剪绳子#
剪绳子
http://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8
算法思想一：动态规划
解题思路：
1、我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
2、用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
3、我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
4、剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
5、第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
6、最后返回dp[n]即可
2、用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
3、我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
4、剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
5、第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
6、最后返回dp[n]即可
代码展示：
Python版本
class Solution: def cutRope(self, number): # write code here # dp[i]标是长度为i的绳子构成乘积的最大值 dp = [0] * (number + 1) dp[2] = 1 for i in range(3, number + 1): for j in range(2, i): # 状态转移公式 dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])) return dp[number]
复杂度分析：
时间复杂度O(N^2)：两重循环，最差的情况下O(N^2)
空间复杂度O(N)：dp数组占用空间
算法思想二：贪心算法
解题思路：
设将长度为 n 的绳子切为 a 段： n=n1+n2+...+na；等价求解：max(n1 x n2 x ... x na )
以下数学推导总体分为两步：① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 3 。
以下数学推导总体分为两步：① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 3 。
推论一： 将绳子以相等的长度等分为多段 ，得到的乘积最大。
设将绳子按照 x 长度等分为 a 段，即 n = ax，乘积为 x^a，由于n 为常数，当 x^(1/x)取最大值时，乘积达到最大值
根据分析，可以将问题转化为求 y = x^(1/x) 的极大值，对 x 求导
取对数 
对x 求导得 
令 
，则1 - ln(x) = 0， x0 = e，且可知 x0 处取得极大值
由于切分长度 x 必须是整数，最接近得数字为 2 或 3，分别计算取得最大值为：
推论二： 尽可能将绳子以长度 33 等分为多段时，乘积最大
切分规则：
最优： 3 ，把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2三种情况。
次优： 2，若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1，若最后一段绳子长度为 1 ；则应把一份 3 + 1 替换为 2 + 2，因为 2×2>3×1
最优： 3 ，把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2三种情况。
次优： 2，若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1，若最后一段绳子长度为 1 ；则应把一份 3 + 1 替换为 2 + 2，因为 2×2>3×1
算法流程：
1、当 n≤3 时，按照规则应不切分，但由于题目要求必须剪成 m>1 段，因此必须剪出一段长度为 1 的绳子，即返回 n−1 。
2、当 n>3 时，求 n 除以 3 的 整数部分 a 和 余数部分 b （即 n=3a+b ），并分为以下三种情况：
当 b = 0 时，直接返回 3^a；
当 b = 1 时，要将一个 1+3 转换为 2+2，因此返回 3^(a-1) x 4；
当 b = 2 时，返回 3^a ×2。
2、当 n>3 时，求 n 除以 3 的 整数部分 a 和 余数部分 b （即 n=3a+b ），并分为以下三种情况：
当 b = 0 时，直接返回 3^a；
当 b = 1 时，要将一个 1+3 转换为 2+2，因此返回 3^(a-1) x 4；
当 b = 2 时，返回 3^a ×2。
图解：
代码展示：
Java版本
public class Solution {
public int cutRope(int target) {
if(target <= 3) return target - 1;
int a = target / 3, b = target % 3;
if(b == 0) return (int)Math.pow(3, a);
if(b == 1) return (int)Math.pow(3, a - 1) * 4;
return (int)Math.pow(3, a) * 2;
}
} 复杂度分析：
时间复杂度O(1)：只有常数级运算
空间复杂度O(1)：变量 a 和 b 使用常数大小额外空间
查看5道真题和解析