题目
给你一根长度为 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:
1
2
3 输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1示例 2:
1
2
3 输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36提示:
2 <= n <= 58
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
拿一个简单的普通例子:$n=5$来具体分析问题,由于每一段绳子长度必须为整数,通过归纳法很容易可以看出:当且仅当第一段绳子的长度等于1时,得到两段绳子的长度乘积大于升子原长$n$。因此,对于一段长度为$n$的绳子,当我们剪下第一段,假设长度为$n1$的绳子时,剩余长度$n_{reamain}$,那么有:
$$
multi = n1\times n_{remain} > n
$$
这时候我们还要不要继续剪呢?很明显,这是一个递归的思路,再剪一次,只要剪出的两端绳子长度均大于1,那么它们的积一定大于$n_{remain}$,得到的乘积$multi$也就越大。因此,最基本的规则是,只要绳子长度大于3,我们就要继续剪,这样一定能得到更优解。
但是怎样才能得到最优解呢?先来考虑一种简单的情况:把一根绳子剪成两段,最大乘积是多少?这个很简单,只要使两段绳子长度相等或最接近即可。而这两端绳子任意一段的长度只要大于3,我们就可以把它化成一个相同的子问题。
到这里答案已经呼之欲出:分治法。
需要注意题目中要求至少剪一次。
在此基础上,我们很容易发现这中间存在重复计算,因此可以使用动态规划自下而上计算。
然而以上解法似乎还是得不到最优解…..从结果归纳来看应该是需要尽可能多的3,拆成尽可能多的3和2的组合。
的确是这样:
1 | class Solution { |
回过头来想想上面的思路(将绳子对半分)其实是贪心算法:每一次计算都企图得到最优解,但最终结果只是局部最优。
而正确的贪心算法应该是尽量剪出长度为3的绳子,而这个需要简单的数学推导:均值不等式
$$
G_{n}=\sqrt[n]{\prod_{i=1}^{n} x_{i}}=\sqrt[n]{x_{1} x_{2} \cdots x_{n}}
$$
$$
A_{n}=\frac{\sum_{i=1}^{n} x_{i}}{n}=\frac{x_{1}+x_{2}+\cdots+x_{n}}{n}
$$
$$
G_{n} \leqslant A_{n}
$$
在本题中,要求的就是$G_n$,而根据均值不等式,$G_n$有上界,因此我们只需要计算其上界,同时注意必须剪一刀的设定。
$$
x_1x_2…x_n\leq (\frac{n}{m})^m
$$
上式中,等号当且仅当$x_1=x_2=…=x_n$时成立,因此
$$
x = \frac{n}{m}
$$
$$
x^m = x^{\frac{n}{x}} = (x^{\frac{1}{x}})^n
$$
令$y=x^{\frac{1}{x}}$,求其极大值:
$$
ln\ y = \frac{1}{x}ln\ x
$$
求导
$$
\frac{1}{y} \dot{y}= \frac{1}{x^2}-\frac{1}{x^2}ln\ x = \frac{1-ln\ x}{x^2}
$$
$$
\dot{y} = \frac{1-ln\ x}{x^2} x^{\frac{1}{x}}
$$
求得极大值点为$x_0=e$,将$2,\ 3$分别带入$y$中,得到$y{|}{x=3}>y{|}{x=2}$。