题目难度: 中等

原题链接

今天继续更新剑指 offer 系列, 这道题和下一道题几乎一样, 不过数据规模小很多. 所以今天就先来一种时间复杂度稍高但比较容易理解的做法, 最优的做法放在下道题 😂

大家在我的公众号"每日精选算法题"中的聊天框中回复 offer 就能看到剑指 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。

  • 2 <= n <= 58

题目样例

示例 1

输入

2

输出

1

解释

2 = 1 + 1, 1 × 1 = 1

示例 2

输入

10

输出

36

解释

10 = 3 + 3 + 4, 3 × 3 × 4 = 36

题目思考

  1. 怎样对题目进行抽象, 提取关键部分?
  2. 如何避免重复计算?

解决方案

思路

分析

  • 先分析题目, 其实这个题目等价于给定一个数, 将其分解成至少两个正数, 求分解后的数的最大乘积
  • 再观察数据规模, N 的范围很小, 所以只要不是指数或更高复杂度的算法(例如O(2^N)), 都完全没问题
  • 注意到一个数的最大乘积是不变的, 所以我们完全可以求得最大乘积后将其保存下来, 用于之后的计算中, 从而避免重复计算, 这就是记忆化搜索的思想
  • 考虑前面几个数, M 大于 1, 意味着 N=2 的时候必须拆分成1*1, N=3 的时候必须拆分为1*2, 这两个都是比原数字更小的, 而当 N>=4 的时候就可以至少拆分成两部分都大于等于 2 的数的乘积了, 这时候两者乘积就会大于等于两者之和
  • 然后对于任意 N>=4 的数, 我们都可以将其拆分成>=2的一段, 而剩余部分当做一个整体求出其最大乘积 (这个最大乘积可能由两段或者更多段相乘得到, 这不是我们关心的重点), 这样就得到了一个拆分的方案; 然后求这些拆分方案中乘积最大的, 就是当前 N 的最大乘积, 将其记录下来以便之后的计算复用

实现

  • 注意 N<=3 的特殊情况, 乘积只能是N-1
  • N>=4 时就要用上记忆化搜索
    • 递归出口: N<=3, 直接返回 N 本身即可. 特别注意这里和上面N<=3并不同, 这里不需要再次拆分, 因为它是更大的数字拆分而来的, 所以自身就是最大值
    • 递归内部: 此时N>=4, 正如上面分析, 先单独拿出一段, 并将剩余部分当做整体, 求两者乘积的最大值. 设单独的一段长度为 i, 那么 i 的取值是[2,N-2], 因为如果切的一段为 1 的话, 其乘积一定比原来的值更小

复杂度

  • 时间复杂度 O(N^2)
    • N 个数都要被递归调用一次, 然后递归内部有 N 的循环, 所以是O(N^2)
  • 空间复杂度 O(N)
    • memo 字典, 以及递归的栈的空间消耗(递归深度是 N)都是O(N)

代码

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3:
            # N<=3必须被拆分, 乘积比原数字恰好都小1
            return n - 1
        memo = {}

        def cut(n):
            if n not in memo:
                if n <= 3:
                    # 递归出口, 最大值就是原数字
                    memo[n] = n
                else:
                    # 先单独拿出一段, 并将剩余部分当做整体, 求两者乘积的最大值
                    mx = 0
                    for i in range(2, n-1):
                        mx = max(mx, i*cut(n-i))
                    memo[n] = mx
            return memo[n]
        return cut(n)

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊

每日精选算法题 - 微信扫一扫关注我