剑指offer—面试题14:剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

动态规划解：

如果面试题是求一个问题的最优解（通常是最大最小值），而且这个问题可以能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决这个问题啦。

这道题目的动态规划解法：首先定义f(n)为把长度为n的设置剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们会有n-1个选择，即剪出来的第一段绳子的长度 i 有1,2,3...，n-1中可能。那么 f(n)=max(f(i)f(n-i)), 其中 0<i<n。我们取第一刀下去后的最大值就是我们解，也是进一步将大问题拆解成子问题： f(i)、f(n-i)。我们继续递归寻找 f(i) 和 f(n-i)的最大值。逼近我们能给出的base case。问题中的base case:f(1) = 1f(2) = 2 f(3) =3（1、2、3时候不去剪绳子最优）。

 func cuttingRope(_ n: Int) -> Int {
        
        if n < 2{
            return 0
        }
        if n == 2 {
            return 1
        }
        if n == 3 {
            return 2
        }
        
        var dp = Array(repeating: 0, count: n+1)
        // 1、2、3长度不划分时候值最大
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        
        var max = 0
        for i in 4...n {
            for j in 1...i/2 {
                let temp = dp[j] * dp[i-j]
                if  max < temp{
                    max = temp
                }
            }
            dp[i] = max
        }
        max = dp[n]
        return max
    }

贪婪算法

当我们使用贪婪算法是，每一步都可以做出一个贪婪的选择，基于这个选择，我们能够得到最优解。贪婪算法的缺点是我们需要找到数学的方式来证明贪婪的正确性。此题中，贪婪算法给出的解释：当 n >= 5时，每次尽可能剪出一段长度为3 的绳子。

class Solution {
    func cuttingRope(_ n: Int) -> Int {
    if n == 2 { return 1}
    if n == 3 { return 2}
    var threeCount = n / 3
    var threeRetain = n % 3
    // 当余1时，回退一个3，将余值凑成4
    if threeRetain == 1 {
        threeCount = threeCount - 1
        threeRetain = 4
    }
    return  Int(pow(Double(3), Double(threeCount))) * (threeRetain == 0 ? 1 : threeRetain)
   }
}

该解法需要数学理论支撑，有兴趣的同学可以看看力扣上的证明！