剑指 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
提示：

解题思路

这个题使用dp来解决。
状态定义：
dp[n]为拆n拆出的所有正整数的最大化乘积。
初始值：
dp[2]=1, dp[3]=2
转移方程：
如果剪完一刀以后，剩下的长度足够长，还可以剪好几刀，怎么办？这时候每一刀除了考虑自己是最后一刀，也要考虑自己是第一刀，而剩下的长度是下一次的第一刀（又要dp了），一直到剩1米或者两米不应该再切了为止。这样，就可以用dp = max(我是最后一刀，我不是最后一刀)。
从dp[4]开始动态规划。
dp[i] = max(之前的最大化乘积, max(剪完j米之后还要继续剪出两米或以上(dp[i-j]×j), 剪完这刀就不剪了或者只再剪一米(j×(i-j))))。
返回值：
dp[n]

解题代码

class Solution:
    def cuttingRope(self, n: int) -> int:
        # dp[n]为拆n拆出的所有正整数的最大化乘积
        dp = [0 for _ in range(n+1)]
        dp[2] = 1
        if n >= 3:
            dp[3] = 2
            # 由于dp[0]和dp[1]不存在，要保证i-j>=2，所以计算每个dp[i] = max(之前的最大化乘积, max(剪完j米之后还要继续剪出两米或以上(dp[i-j])来, 剪完这刀就不剪了或者只再剪一米))
            # j最小为2，如果i从3开始，dp[i-j]可能会到dp[1],所以i循环从4开始,这样i-j最低也是dp[2]
            for i in range(4, n+1):
                # 一刀下去，剪的长度为j米
                for j in range(2, i-1):
                    dp[i] = max(dp[i], max(dp[i-j]*j, j*(i-j)))
        return dp[n]

执行结果

64ms 18.2MB