剪绳子

题目：给你一根长度为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。

动态规划

需要O(n²)时间和O(n)空间

func maxProductAfterCutting_solution1(_ length: Int) -> Int {
    if length < 2 {
        return 0
    }
    if length == 2 {
        return 1
    }
    if length == 3 {
        return 2
    }
    
    var products = [Int](0...length) // 子问题的最优解存储的数组。数组中第i个元素表示把长度为i的绳子剪成若干段之后各段长度乘积的最大值。
    var max: Int = 0
    
    for i in 4...length {
        max = 0
        for j in 1...(i / 2) {
            let product = products[j] * products[i - j]
            if max < product {
                max = product
            }
            products[i] = max
        }
    }
    
    max = products[length]
    return max
}

贪婪算法

当n≥5时，我们尽可能多地剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。

func maxProductAfterCutting_solution2(_ length: Int) -> Int {
    if length < 2 {
        return 0
    }
    if length == 2 {
        return 1
    }
    if length == 3 {
        return 2
    }
    
    // 尽可能多地剪去长度为3的绳子段
    var timesOf3: Int = length / 3
    
    // 当绳子最后剩下的长度为4的时候，不能再剪去长度为3的绳子段
    // 此时更好的方法是把绳子剪成长度为2的两段，因为 2×2 > 3×1
    if length - timesOf3 * 3 == 1 {
        timesOf3 -= 1
    }
    
    let timesOf2: Int = (length - timesOf3 * 3) / 2
    
    let max: NSNumber = pow(3, timesOf3) * pow(2, timesOf2) as NSNumber
    
    return max.intValue
}

摘抄资料：《剑指offer》