剪绳子｜刷题打卡-一一网

掘金团队号上线，助你 Offer 临门！点击查看详情

一、题目描述

给你一根长度为 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
复制代码

二、思路分析

我的思路

列出所有的剪法（最笨的可以计算所有的剪法，这里的所有指的是7,1 1,7 都算一次）
- 长度为n的话，那么最多就可以砍n-1刀
- 那么所有的可能：
  - 1 刀就可以放在 C(n-1,1) 种剪法
  - …
  - n-1 到就是 C(n-1, n-1) = 1 种剪法
  - 所以一共有C(n-1, 1) + … C(n-1, n-1) 种剪法 == 这个能算么？怎么算来着？(⊙_⊙)?
- 找出乘积最大的那个值
是否有数学的方式直接求解的？或者有什么数学规律在这乘积最大剪法里面？这种直觉很强烈！

最佳思路

果然有数学算法：利用立一个算术几何均值不等式 => 可以推论出尽可能等分，得到的乘积最大
- 那么新问题，等分尺度多大？1的话就是最小了，通过一列计算求极值，得出尺度为3面积最大，所以：
  - n <= 3
    - 因为n>1 所以减去一刀1 和 n-1 返回n-1
  - n > 3
    - 先按3分还还余几？
    - 余0：直接就是均分 3^n/3
    - 余1: 需要拆出一个3和1 整合为 2×2 因为2×2>3×1
    - 余2: 不要再减了，就 3^(n/3)x2
- 这样复杂度就是O(1)
还可以使用递归法
- 这个是我应该能想出来的。。。。就是没要剪开一刀的时候都2种情况：剪开和不减，剪开就递归，然后求这2个最大值，取最大值。

三、AC 代码

我的写法：

列出所有的可能：

可能结果其实是一棵树：2刀有几种， 2刀之后，两半都可以来一刀，往下递归。

注意：在任意一步上我们都可以2个选择： 1. 继续减下去， 2 不减了，就使用当前的状态做乘积。所以递归开始回弹的时候，我们需要取这2种方法的最大值，比如最后剪到2的时候，我们可以减成1×1 也可以就是2不动了。继续减成1×1就是继续往下递归，所以递归的函数 F(n)=max(i*(n-i),i* F(n-i))。
但是这个解法超时了 ?


public int cuttingRope(int n) {
    if (n <= 2) {
        // 不能再切了，或者说只有一种切法1x1
        return 1;
    }
    // 存放结果
    int res = 0;
    // 长度为n的绳子，可以从2开始切，一共也会有n-2个切法
    // 因为1*F(n-1) 和 1 *（n-1） F(n-1) >= (n-1) 就不可能剪出一个1出来的，除非初始就是2或者3 不然 你如果剪出1个1，那么就等于没有价值，也就等于n-1长度的绳子有怎么减最大
    // （其实尾部也是一样的不是吗？所以应该i<n-1也行）
    for (int i = 2; i < n; i++) {
        // 这max是获取递归下面最终获取到的最大结果  即：继续减下去的结果 i * cuttingRopeMath(n - i) 和 不再继续减下去 i * (n - i) 哪一个大
        int max = Math.max(i * cuttingRopeMath(n - i), i * (n - i));
        if (max > res) {
            //这个比较是 在这一层上 一共有n-2种切法，这n-2种切法 的最大值
            res = max;
        }
    }
    return res;
}
复制代码

最佳写法：

数学方法

public int cuttingRopeMath(int n) {
    if (n <= 3) {
        return n - 1;
    }
    int a = n / 3, b = n % 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;
}
复制代码

递归方法

/**
 * 递归记忆化
 * 空间换时间
 * <p>
 * 当递归 i* f(n-i) 的时候，我们会重复计算很多次f(n-i) 比如：n=4 ->1xf(3) = 1x1xf(2) 和 2xf(2) 那么这个f(2)就算2次了，我们可以第二次算这个使用记录值
 */
public int cuttingRopeBetter(int n) {
    int[] member = new int[n + 1];
    member[2] = 1;
    return cut(member, n);
}
public int cut(int[] member, int n) {
    // 之前已经算过了f(n)
    if (member[n] != 0) {
        return member[n];
    }
    int res = 0;
    for (int i = 2; i < n; i++) {
        int max = Math.max(i * cut(member, n - i), i * (n - i));
        if (max > res) {
            res = max;
        }
    }
    // 这个算出来的结果放入member记录
    member[n] = res;
    return res;
}
复制代码