劍指offer：剪繩子

題目：
給定一根長度為n的繩子，請把繩子剪成m段（m、n都是整數，n>1并且m>1），每段繩子的長度記為k[0],k[1],…,k[m]。請問k[0] k[1] … *k[m]可能的最大乘積是多少？

例子：
例如，當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18。

def cutRopeDP(length):
    """
    在剪繩子這個題目中，由于必須要剪一刀，因此會導致當所給的繩子長度是小于4的時候，剪完之后的長度
    小于剪之前的長度。但是我們在遞推的時候，例如求f(5) = max{f(1)*f(4), f(2)*f(3)} = 6
    如果令f(3)=2的話，將導致遞推公式錯誤，因此，對于小于4的輸入，我們特殊處理。
    """
    if length < 2:  # 由于至少剪一刀，所以當長度小于2的時候無法剪，因此返回0
        return 0
    if length in (2, 3):
        return {2: 1, 3: 2}[length]

    products = [0, 1, 2, 3]  # 初始化長度小于4的輸入所對應的輸出的最大值
    for i in range(4, length + 1):
        max_product = 0
        # 對于每一個輸入，我們需要遍歷它所有可能的輸出然后挑出最優的
        for j in range(1, i // 2 + 1):
            max_product = max(max_product, products[j] * products[i - j])
        products.append(max_product)

    return products[-1]

def cutRopeGreedy(length):
    """
    當n>=5的時候，2(n-2) > n and 3(n-3) > n; 3(n-3) >= 2(n-2)
    也就是說當長度大于5的時候，剪出長度為3的段數越多最后的乘積越大

    但是對于長度為4的時候，如果剪出一段長度為3，另一段長度為1，則乘積為3，小于剪出兩段長度為2
    因此，當最后剩下4的時候，不是剪成1,3而是剪成2,2

    但是使用貪心方法求解最優解的時候需要非常tricky，因此優先嘗試dp吧
    """
    if length < 2:  # 由于至少剪一刀，所以當長度小于2的時候無法剪，因此返回0
        return 0
    if length in (2, 3):
        return {2: 1, 3: 2}[length]
    timesOf3 = length // 3
    if length - timesOf3 * 3 == 1:
        timesOf3 -= 1
    timesOf2 = (length - timesOf3 * 3) // 2
    return 3 ** timesOf3 * 2 ** timesOf2