【Python】剑指offer 14：剪

#面试题14：剪绳子
class Solution:
    def dynamic_programming(self, n):
        if n < 2:   #长度<2，为0
            return 0
        if n == 2:  #长度=2，剪成两段1
            return 1
        if n == 3:  #长度=3,1x2
            return 2
        tmp_lst = [0, 1, 2, 3]
        for i in range(4, n+1):     #长度>4
            max = 0
            for j in range(1, i):   #从下往上分析问题
                tmp = tmp_lst[j] * tmp_lst[i - j]
                if max < tmp:
                    max = tmp
            tmp_lst.append(max)
        return tmp_lst[n]

s = Solution()
print(s.dynamic_programming(8))