14 剪绳子

注：1到3是特殊情况

class Solution():
    def cutrope(self,k):
        A = [0]*(k+1)
        A[1] = 1
        A[2] = 2
        A[3] = 3
        if k <2:
            return 0
        if k ==2:
            return 1
        if k ==3:
            return 2
            
        else:
            for i in range(4,k+1):
                for j in range(1,int(i/2)+2):
                    A[i] = max(A[i],A[j]*A[i-j])

            return A[k]



#test
s = Solution()
print(s.cutrope(8))