剑指 Offer 14- II. 剪绳子 II

题目描述

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：
2 <= n <= 1000

链接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof
注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

解题思路

n长的绳子相当于一个n的正整数，dp[i]表示i长的绳子使用各种方式截断后的最大乘积
状态转移：
- 遍历j=1..i-1,则绳子可以分为j和i-j两部分,假设i-j也可以被分
- dp[i] = max(j(i-j),jdp[i-j])
- 取其中最大的dp[i]
- 返回结果：dp[n]%1000000007

解题代码

class Solution:
    def cuttingRope(self, n: int) -> int:
        # dp[i]为切长度为i的绳子的时候的最大乘积
        dp = [0]*(n+1) # 没有dp[0]，从dp[1]到dp[n]
        # 总长度为i
        for i in range(2,n+1):
            # 切出来j
            for j in range(1, i):
                # dp[i] = max(之前切出来j不同的时候的最大乘积dp[i]，剪掉j以后不在继续拆分的时候的乘积j*(i-j)，剪掉j以后还继续拆分i-j的时候的乘积j*dp[i-j])
                dp[i] = max(dp[i],j*(i-j),j*dp[i-j])
        return dp[n]%1000000007

执行结果

执行结果：通过
执行用时：656 ms, 在所有 Python3 提交中击败了18.38%的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了33.99%的用户