题解 | #剪绳子#

class Solution:
    def cutRope(self , n: int) -> int:
        # write code here
        dp = [ 0 for _ in range(n+1)]
        for i in range(2,n+1):
            for j in range(1,i):
                dp[i] = max(dp[i],j*max(dp[i-j],i-j))
        return dp[-1]

首先要找到n前面所有绳子的剪开乘积：

第一个for循环：从2开始到n长度的绳子的所有情况，当前绳子为长度为i的绳子；

再找到当前对应的绳子的动态转移方程：

第二个for循环：长度为i的绳子，剪开的所有剪法是i-1种，从剪下1一直到剪下i-1，这个数字记为j

动态转移方程：

长度为i的绳子，剪下来的最大乘积，要从这i-1种剪法中找。

1.首先判断dp[i-j]与i-j的最大值

（1）长度i的绳子剪下长度j后，比较：长度为i-j的绳子的本身长度 vs 长度为i-j绳子的剪后最大乘积

（2）最大值为我们需要的i-j长度绳子的最大乘积

2.其次判断对于长度为i绳子的最大乘积

（1）根据上述分析，需要将剪下的长度j和对应的剩余最大乘积累乘在一块，即j*max(dp[i-j],i-j)

（2）其次，取所有的j取值（j=1,...,n-1）的最大值：max(dp[i],j*max(dp[i-j],i-j))

因此，最后的转移方程为：dp[i] = max(dp[i],j*max(dp[i-j],i-j))

最后返回dp数组中的最后一位即可。