剪绳子问题（动态规划求解）

给你一根长度为 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法：动态规划
状态定义：dp为一维数组，其中dp[i] (i>=4)数值代表长度为i的绳子可能的最大乘积。
转移方程：dp[i]=max(dp[i-1]*1, dp[i-2]*2, …)允许条件为dp[a]*b里面的数值a必须大于等于所乘积的数值b。
初始条件：dp[2]=2, dp[3]=3
特判：当i=2和3的时候，实际答案为1和2
返回值：dp[n]

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
        dp = [0] * (n+1)
        dp[1]=1
        dp[2]=2
        dp[3]=3
        for c in range(4,n + 1):
            i = c - 1
            j = 1
            sum = c
            while j <= i:
                s = dp[i] * dp[j]
                sum = s if s > sum else sum
                i -= 1
                j += 1
            dp[c] = sum
        return dp[n]

本文地址：https://blog.csdn.net/qq_43343275/article/details/107483335