剑指 Offer 14- I. 剪绳子

大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 14-I. 剪绳子。

题目汇总链接：https://www.algomooc.com/jianzhioffer

一、题目描述

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

二、题目解析

我们依旧用 四步分析法 进行结构化的分析，帮助我们思考和发现规律，写出合理的代码。

• 模拟：模拟题目的运行。
• 规律：尝试总结出题目的一般规律和特点。
• 匹配：找到符合这些特点的数据结构与算法。
• 边界：考虑特殊情况。

1、模拟

我们假设绳子的长度为 10。

先来剪一下，假设一开始剪下来的长度为 1，那么左边绳子的长度为 1，右边绳子的长度为 9，它们的乘积为 1 * 9 = 9。

对于一段一开始长度为 10 的绳子而言，9 是小于 10 的，因此剪下长度为 1 的绳子是无法增大乘积的，更一般的来说，1 和任何数相乘都是那个数本身，因此对于任意长度的绳子来说都不应该剪长度为 1 的绳子下来。

数学证明：n > ( n - 1) * 1。

所以，每次剪绳子的操作都是剪至少长度为 2 的绳子的操作。

当剪下一段长度为 2 的绳子时，剩下的绳子长度为 8。

那么对于长度为 8 的这段绳子来说，它有两个选择，剪或者不剪。

• 不剪，乘积结果为 2 * 8 = 16；
• 剪，怎么剪？

对于这两个选择，我们无法第一时间做出决定，因为目前还不知道剪的情况下能否出现大于 16 的结果。

所以，接下来的操作就是去剪第二段绳子。

怎么剪呢？

和剪长度为 10 的那段绳子一样的思路。

剪完之后，第二段绳子也被划分两块区域，a 和 b。

通过剪长度为 10 的绳子与长度为 8 的绳子的操作，我们可以发现：我们在不停的去剪相对的那根 第二段 的绳子，直到剪无可剪为止。

此时我们考虑第二段的情况时，第一段绳子的长度为 2，而事实上，第一段绳子可取的范围为 [ 2，i）。

假设当下绳子的长度为 i

2、规律

长度为 n 的绳子剪掉后的最大乘积与求绳子长度为 n - 1 、 n - 2 、 n - 3 的最大乘积求法一样。

不会剪长度为 1 的绳子下来。

假设剪的绳子那段称为 第一段，剪剩下的那段绳子称为 第二段，那么第一段的范围为 [2,i)，第二段可以剪或者不剪，假设 dp[i] 表示长度为 i 的绳子剪成 m 段后的最大乘积，那么，不剪总长度乘积为 j * （ i - j），剪的话长度乘积为 j * dp[ i - j ]，取两者的最大值，即 Max ( j * ( i - j) , j * dp[ i - j] )。

3、匹配

通过规律可以发现，本题具备以下几个特征：

• （1）是求最优解问题，如最大值，最小值；
• （2）该问题能够分解成若干个子问题，并且子问题之间有重叠的更小子问题。

动态规划！

状态： dp[i]

状态转移方程：dp[i] = Max(dp[i], Max(j * (i - j), j * dp[i - j]))

4、边界

• 长度为 1 的绳子
• 长度为 2 的绳子

三、动画描述

四、图片描述

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public int cuttingRope(int n) {
        // 长度为 1 的绳子没法剪了
        if ( n <= 1 ) return 1;
        // 用一个名为 dp 的数组来记录从 0 到 n 长度的绳子剪掉后的最大乘积
        // 默认都是 0
        int[] dp = new int[n + 1];
        // 由于绳子必须被剪，所以长度为 2 的绳子只有剪成 1 和 1 的两段，乘积结果为 1
        dp[2] = 1;
        // 长度大于等于 3 的绳子才开始进入我们的讨论范围
        // 从长度为 3 的绳子开始考虑，讨论它的最大乘积是多少，并不断的延伸绳子的长度
        for(int i = 3; i < n + 1; i++){
            // 对于长度为 i 的绳子，它可以分为两个区间 j 和 i - j
            // j 的范围由 2 开始，因为剪长度为 1 的绳子无法扩大乘积的值
            // j 的范围可以延伸至 i - 1
            for(int j = 2; j < i; j++){
                // 不剪总长度乘积为  j * （ i - j）
                // 剪的话长度乘积为  j * dp[ i - j ]
                // 取两者的最大值，即  Max ( j * ( i - j) , j * dp[ i - j] )
                // 那么此时 dp[i] 的值取 i 不剪的值（ dp[i]) 和剪的值 Math.max(j * (i - j), j * dp[i - j]) 这两者的最大值
                // 比如一开始 i = 3 ， j = 2
                // dp[3] = Math.max( 0 ,Math.max ( 2 * 1, 2 * dp[1])
                //       = Math.max( 0 ,Math.max ( 2, 2))
                //       = 2
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(n²) 。

空间复杂度

空间复杂度为 O(n) 。

七、相关标签

• 动态规划
• 数学

八、参考链接

1、https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

2、https://www.algomooc.com/jianzhioffer

程序员吴师兄算法训练营永久会员

打赏 收藏 海报 链接