解题思路

可以线从简单的情况进行分析：

• 当绳子长度为2和3的时候，不切分的乘积是最大的；当绳子长度为4的时候，对半切分的乘积是最大的。
• 而继续往后计算的话，有一个规律：假设一段长为i的绳子，其后j段不能切分，那么我们知道它前面i-j长的绳子切分乘积最大值，则我们可以知道最终的乘积，一个一个去比较大小，取大值。

复杂度

• 时间复杂度为O(N）；
• 空间复杂度为O(N)。

代码

Python

class Solution:
    def cutRope(self , n: int) -> int:
        # write code here
        if n < 4:
            return n

        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        dp[4] = 4
        for i in range(5, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], j*dp[i-j])

        return dp[-1]

C++

class Solution {
public:
    int cutRope(int n) {
        // write code here
        if(n<4)
        {
            return n;
        }

        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;

        for(int i = 5; i < n+1; i++)
        {
            for(int j = 1; j < i; j++)
            {
                dp[i] = max(dp[i], j*dp[i-j]);
            }
        } 
        return dp[n];
    }
};