题解 | #剪绳子#

剪绳子

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]即可

代码展示：

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 。

推论一：将绳子以相等的长度等分为多段，得到的乘积最大。

设将绳子按照 x 长度等分为 a 段，即 n = ax，乘积为 x^a，由于n 为常数，当 x^(1/x)取最大值时，乘积达到最大值

$x^{a}=x^{\frac{n}{x}}=(x^{\frac{1}{x}})^{n}$

根据分析，可以将问题转化为求 y = x^(1/x) 的极大值，对 x 求导

取对数 $lny = \frac{1}{x}lnx$

对x 求导得 $\bar{y} = \frac{1-lnx}{x^{2}}x^{\frac{1}{x}}$

令 $\bar{y}=0$ ，则1 - ln(x) = 0， x0 = e，且可知 x0 处取得极大值

由于切分长度 x 必须是整数，最接近得数字为 2 或 3，分别计算取得最大值为：

$y(3)\approx1.44，y(2)\approx1.41$

推论二：尽可能将绳子以长度 33 等分为多段时，乘积最大

切分规则：
    最优： 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。

图解：

代码展示：

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;
    }
}