# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2

        product = [0, 1, 2, 3]

        for i in range(4, number + 1):  # 外循环自下而上确定每个长度的最优值
            maxValue = 0
            # 内循环确定本次长度的最优值，其中只要循环i长度的一半即可，后面一半是重复前面一半的情况
            for j in range(1, i//2 + 1):
                temp = product[j] * product[i - j]
                if maxValue < temp:
                    maxValue = temp
            product.append(maxValue) # 放内循环外边，确保添加进去的是最大值

        maxValue = product[number]
        return maxValue