剑指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

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

二、思路

看大佬解析

1. 暴力法

将绳子剪成m段，那么每段绳子的长度k[0],k[1]...k[m-1]趋近于相等时，也就是说将绳子在分成m段的时候，尽可能的均分，这个时候的每段绳子的乘积是最大的。

那么将绳子分为m段，那么m又该是多少呢？根据题意可以知道2 <= m <=n。所以可以对这些分法进行计算，然后计算出最大值即可。

现在计算每种分法下的每段长度，以及乘积res。我们绳子的长度n除以m取整（就是采用等分的原则）。如果余数为0，那就说明可以等分，res = k[0] ** m。如果不能等分，就需要将第一段的长度减去n -= k[0]，然后对剩余的长度与m-1继续进行等分。

最后返回res。

2. 动态规划

在剪绳子的过程中，我们假设剪下来的的第一段绳子长度为k[0]，那么剩下的一段长度为k[1]。接下来就是就是判断k[0]和k[1]是否可分，以及在各种剪法的组合下，达到乘积的最大值。到这里我们便可以发现实际上就是求k[0]的最大值，与k[1]的最大值，然后相乘。

我们创建一个一位数组dp，用来保存绳子长度为[2, n]分别对应的最大乘积。

状态转移方程为：
$$
dp[i] = max(j, dp[j]) * max(i-j, dp[i-j])
$$
方程中，i表示当前绳子的长度，j表示k[0]，也就是第一段绳子长度。

最后，dp数组最后一个元素便对应着我们需要求的绳子长度的所有剪法的最大乘积。

改进：

随着第一段绳子的长度j达到绳子长度i的一半的时候，再向后j与i-j的组合实际上在前边已经出现过了。例如，当前绳子长度为i = 5，第一段长度j为2，此时i-j为3。那么当j大于i / 2，也就是i的一半的时候，例如j = 3，此时i-j = 2。这个时候实际上就已经没必要接着向下运算了。

三、代码

1. 暴力法

class Solution:
    def cuttingRope(self, n: int) -> int:
        res = 1
        for m in range(2, n+1):
            new_n = n
            # 记录当前分法下的乘积
            cur = 1
            while m >= 2:
                num, mod = divmod(new_n, m)
                if mod == 0:
                    cur *= num**m
                    new_n = 1
                    # 可以等分，所以不需要再进行下去了
                    m -= m
                else:
                    new_n -= num
                    cur *= num
                    m -= 1
            cur *= new_n
            if cur > res:
                res = cur
        return res

2. 动态规划

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 保存对应长度下，最大乘积值
        dp = [0 for _ in range(n + 1)]
        # 绳子长度
        for i in range(2, n+1):
            # 剪下来的第一段绳子长度
            for j in range(1, i):
                cur = max(j, dp[j]) * max(i-j, dp[i-j])
                # 保留最大值
                dp[i] = max(cur, dp[i])
        return dp[-1]

修改：

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0 for _ in range(n + 1)]
        for i in range(2, n+1):
            for j in range(1, i // 2 + 1):
                cur = max(j, dp[j]) * max(i-j, dp[i-j])
                dp[i] = max(cur, dp[i])
        return dp[-1]

四、表现

method	运行时间	表现	内存消耗	表现
1. 暴力法	40ms	79.64%	13.5MB	5.53%
2. 动态规划	48ms	39.11%	13.5MB	5.01%
2.2 动态规划修改	40ms	79.82%	13.5MB	6.64%