题目描述

剑指 Offer 14- I. 剪绳子

难度中等

给你一根长度为 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

测试用例

• 功能测试（绳子的初始长度大于5）
• 边界值测试（绳子的初始长度分别为0、1、2、3、4）

题目考点

• 考察应聘者的抽象建模能力。应聘者需要把一个具体的场景抽象成一个能够用动态规划或者贪婪算法解决的模型。
• 考察应聘者对动态规划和贪婪算法的理解。能够灵活运用动态规划解决问题的关键是具备从上到下分析问题、从下到上解决问题的能力，而灵活运用贪婪算法则需要扎实的数学基本功。

解题思路

思路一：动态规划

这题用动态规划是比较好理解的

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

代码

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i < n + 1; i++){
            for(int j = 2; j < i; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

贪婪算法

尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现，如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。

证明：

当 n >= 5 时，所有f(n)都可以表示为3(n - 3)或者2(n - 2)，又因为3(n - 3) - 2(n - 2) = n - 5 >= 0。因此把长度大于 5 的绳子切成两段，令其中一段长度为 3 可以使得两段的乘积最大。

当 n = 4时，拆成 2 * 2 最大。

class Solution {
    public int cuttingRope(int n) {
        if(n<4)
            return n-1;
        int a = n%3;
        int b=n/3;
        if(a==0)return (int)Math.pow(3,b);
        if(a==1)return (int)Math.pow(3,b-1)*4;
        return (int)Math.pow(3, b) * 2;

    }
}

补充

动态规划

如果面试题是求一个问题的 最优解（通常是求最大值或者最小值）（特点一），而且该问题 能够分解成若干个子问题（特点二），并且 子问题之间还有重叠的更小的子问题（特点三），就可以考虑用 动态规划 来解决这个问题。从上往下分析问题，从下往上求解问题，这是动态规划求解的问题的第四个特点。

贪婪算法

当我们应用贪婪算法解决问题的时候，都一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。为什么某种贪婪选择能够得到最优解？ 这是我们应用贪婪算法时都需要问的问题，需要用数学方式来证明贪婪选择是正确的。