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

注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

来源：力扣（LeetCode）

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、 动态规划

动态规划是面试中的热门话题。

2.1 什么样的场景适合动态规划呢？

• 如果题目是：

  • 求一个问题的最优解（通常是最大值或者最小值）

  • 而且改问题能够分解为若干个子问题

  • 并且字问题之间还有重叠的更小的子问题

• 就可以考虑使用动态规划来解决这个问题

2.2 本题是否适合动态规划？

• 我们把长度为n的绳子剪成若干段后得到的乘积的最大值定义为函数f(n)。

• 假设我们把第一刀剪在了长度为i（0 < i < n）的位置，于是把绳子剪成了长度为i和n-i的两段。

• 我们想要得到整个问题的最优解f(n)那么要同样用最优化的方法把长度为i和n-i的两段分别剪成若干段，使得各自剪出的每段绳子的乘积最大。

• 也就是说整体问题的最优解是依赖各个子问题的最优解。

2.3 动态规划的过程

• 由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，我们可以：

  • 从下往上的顺序先计算小问题的最优解并存储下来

  • 再以此为基础求取大问题的最优解

• 这种从上往下分析问题，从下往上解决问题也是动态规划的一大特征。

2.4 应用在本题中

在应用动态规划的时候，我们每一步都可能面临若干个选择。

本题中：

• 第一刀有n-1种选择。我们可以剪再 1,2...n-1 的任意位置。

• 由于我们事先不知道那个位置是最优解，只好把所有可能的额都尝试一遍，然后比较出最优解。

• 用数学表示就是

  • f(n) = max(f(i), f(n-i))

  • 0 < i < n

代码

func cuttingRope(_ n: Int) -> Int {
    if n < 4 {
        return n - 1
    }
    var dp = [Int](repeating: 1, count: n + 1)
    for i in 3...n {
        for j in 2..<i {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        }
    }
    return dp[n]
}

时间复杂度	空间复杂度
O(n^2)	O(n)

三、 贪婪算法

贪婪算法和动态规划不一样。当我们应用贪婪算法解决问题的时候，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。

至于为什么这样的贪婪选择能够得到最优解。这就需要使用数学方式来证明了。

3.1 应用再本题中

• 如果绳子长度大于5，则每次都剪出一段长度为3的绳子。

• 如果剩下的长度仍然大于5，则接着剪出一段长度为3的绳子。

• 循环

• 直到剩下的绳子长度小于5。

  • 当绳子长度为4时，剪成 2x2=4

  • 当绳子长度为3时，剪成 1x2=2

  • 当绳子长度为2时，剪成 1x1=1

    • 其实不剪最大，但要求至少剪一刀那就剪呗

剪出一段长度为3的绳子就是我们在每一步做出的贪婪选择。

3.2 证明上面思路的正确性

• 当n>=5时

  • 2(n-2)>n && 3(n-3)>n

  • 也就是说当绳子的长度大于或等于5时，我们可以把它剪成3或2的绳子段

• 另外当n>=5

  • 3(n-3)>=2(n-2)

  • 因此我们应该尽可能多的剪长度为3的绳子

上面时原书中的解释，更详细专业的证明Krahets

代码

func cuttingRope(_ n: Int) -> Int {
    if n < 2 {
        return 0
    }
    if n == 2 {
        return 1
    }
    if n == 3 {
        return 2
    }

    // 3长度的最大段数
    var threeCount = n / 3

    // 当绳子剩下4的时候 不能再剪3长度，更优的方式是剪成长度为2的，因为 2x2 > 3x1
    if n - threeCount * 3 == 1 {
        threeCount -= 1
    }
    let twoCount = (n - threeCount * 3) / 2

    return Int(truncating: NSDecimalNumber(decimal: pow(3, threeCount))) * Int(truncating: NSDecimalNumber(decimal: pow(2, twoCount)))
}

时间复杂度	空间复杂度
O(1)	O(1)