题解 | #剪绳子#

题目：https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8

法一：动态规划

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def cutRope(self , n: int) -> int:
        # f(1)=1,f(2)=2,f(3)=3,f(4)=4,f(5)=6
        # 数列中找不出上面规律        
        # 因为需要考虑每步能得到的最大乘积，那就需要一个记录下每步最优的n*1的数组dp.
        # 只剪掉长度为1，对最后的乘积无帮助。从长度4开始剪才有用。
        #长度为i的绳子，剪一段j长度。
        #dp[i]=max(dp[i],d[i-j]*dp[j])，比如dp[5]=dp[1]*dp[4]或者dp[2]*dp[3].分解下来的dp也是可以继续分解的
        if n==2:
            return 1
        if n==3:
            return 2
        dp=[0]*(1+n)
        dp[1]=1
        dp[2]=2
        dp[3]=3
        #i大于等于4的情况，2、3不切分，所以dp[2]=2，dp[3]=3
        for i in range(4,n+1):
            for j in range(2,n//2): #j切到一半就可以了，另一半的结果也是对称的
                dp[i]=max(dp[i],dp[i-j]*dp[j])
        return dp[n]

时间复杂度：O(n2)，两层遍历

空间复杂度：O(n)，辅助数组dp的空间

法二：数学公式。 要使乘积最大，应该以相等的长度等分成多段。找这个最优长度是多少。最优长度是e。

class Solution:
    def cutRope(self , n: int) -> int:
        if n==2:
            return 1
        if n==3:
            return 2
        if n==4:
            return 4
        res=1
        while n>4:
            #如果n大于4，我们不停的让他减去3。不能n取等于4，因为2*2>1*3，所以剩下是4时不要剪成1和3.
            n=n-3
            res=res*3
        #最后剩下的n去成res
        return n*res

时间复杂度：O(n)，其中n为绳子的长度，最坏需要计算n/3次

空间复杂度：O(1)，常数级变量，无额外辅助空间