剪绳子

def cutRope(length):
    if length == 0:
        return 0
    if length == 1:
        return 1
    if length == 2:
        return 2
    if length == 3:
        return 3
    if length == 4:
        return 4
    result = [0,1,2,3]
    for i in range(4,length+1):
        max = 0
        for j in range(1,i//2+1):
            temp = result[j] * result[i-j]
            if temp > max:
                max = temp
        result.append(max)
    return result[length]
print(cutRope(8))
# 动态规划

# 贪心算法
def cutRope(length):
    if length <= 4:
        return length
    timeOfThree = length // 3
    if length - timeOfThree * 3 == 1:  
    # 如果减去3，还剩下4，这时候就不能在减去3了，2*2 > 3 * 1
        timeOfThree -= 1
    timeOfTwo = (length - timeOfThree * 3) // 2
    return pow(3,timeOfThree) * pow(2,timeOfTwo)

func cutRope(n int) int {
   if n<2 || n > 60 {
      return 0
   }
   if n == 2 {
      return 1
   }
   if n == 3 {
      return 2
   }
   if n == 4 {
      return 4
   }
   return 3*cutRopeHandler(n-3)
}

func cutRopeHandler(n int) int {
   if n == 2 {
      return 2
   }
   if n == 3 {
      return 3
   }
   if n == 4 {
      return 4
   }
   return 3*cutRopeHandler(n-3)
}