Integer Break

题目介绍

LeetCode 343. Integer Break。

复杂度

• 动态规划：时间复杂度: O(n*n), 空间复杂度: O(n)
• 贪婪算法：时间复杂度: O(1), 空间复杂度: O(1)

解题思路

动态规划

边界条件：dp[1] = dp[2] = 1，表示长度为 2 的绳子最大乘积为 1；
状态转移方程：dp[i] = max(dp[i], max(dp[i-j] * j, (i - j) * j))

dp[i] = 维持原状态，不剪
dp[i-j] * j = 从 j 处剪一下，减下来的部分是 i-j，i-j 继续剪
(i-j) * j = 从 j 处剪一下，减下来的部分是 i-j，i-j 不再剪了

class Solution {
    func integerBreak(_ n: Int) -> Int {
        if n < 3 {
            return n - 1
        }
        var dp: [Int] = Array(repeating: 0, count: n + 1)
        dp[2] = 1
        for i in 3...n {
            for j in 1..<i {
                /**
                 dp[i] = 维持原状态，不剪
                 dp[i-j]*j = 从 j 处剪一下，减下来的部分是 i-j，i-j 继续剪
                 (i-j)*j = 从 j 处剪一下，减下来的部分是 i-j，i-j 不再剪了
                 */
                dp[i] = max(dp[i], max(dp[i-j] * j, (i - j) * j))
            }
        }
        return dp[n]
    }
}

贪婪算法

切分规则：
最优： 3 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2 三种情况。
次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1 。若最后一段绳子长度为 1 ；则应把一份 3 + 1 替换为 2 + 2，因为 2×2>3×1。

class Solution {
func integerBreak(_ n: Int) -> Int {
// 当 n≤3 时，按照规则应不切分，但由于题目要求必须剪成 m>1 段，因此必须剪出一段长度为 1 的绳子，即返回 n−1 。
if n < 3 {
return n - 1
}
let a = n / 3
let b = n % 3
if b == 0 {
return NSDecimalNumber(decimal: pow(3, a)).intValue
} else if b == 1 {
return NSDecimalNumber(decimal: pow(Decimal(3), a - 1) * 4).intValue
} else {
return NSDecimalNumber(decimal: pow(3, a) * 2).intValue
}
}
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/06/28/IntegerBreak/