343. 整数拆分 [medium]

https://leetcode-cn.com/problems/integer-break/

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

通过次数53,029 | 提交次数90,896

Second Try

2020-07-30

没想到这题还能够用DP来做，虽然是O(N^2)的复杂度?

好像复杂度有点难算啊，dp(n)需要计算dp(1..n)，总共n次。而对每一个dp(i)自身,还需要比较i次。因此总共是O(N^2)次。

特别注意 dp[n-i]还需要与n - i进行对比，因为dp[n - i]被强制拆为两个数字，可能比n - i还小。比如dp[2]和2.

class Solution:
    def integerBreak(self, n: int) -> int:
        # DP暴力

        dp = [""] * (n + 1)
        dp[1] = 1
        def max_break(n):
            if dp[n] != "":
                return dp[n]
            t = 0 
            for i in range(1, n):
                # dp[n-i]还需要与n - i进行对比，因为dp[n - i]被强制拆为两个数字，可能比n - i还小。比如dp[2]和2.
                t = max(t, i * max(n - i, max_break(n - i)))
            dp[n] = t 
            return dp[n]
        rv = max_break(n)
        # print(dp)
        return rv

执行用时：56 ms, 在所有 Python3 提交中击败了12.14%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了64.71%的用户

First Try

记得把固定周长的拆分为等分长度的乘积最大，这个好像是算数平方公式？

也是神奇，按切分份数来分： 8切分2，3，4份，分别是4 2， 2 3 2， 2 4, 愣是没有3 2 2. 因此才需要额外一步:

if val >= 2:
    maxrv = max(maxrv,  s ** val * additional)

class Solution:
    def integerBreak(self, n: int) -> int:
        # 还是上暴力法吧 

        maxrv = 0
        split_start = 2
        split_end = max(split_start, n // 2) # n = 2/3的时候，就靠这个
        for s in range(split_start, split_end + 1):
            val, res = divmod(n, s)
            additional = 1 
            if res == 1:
                s -= 1
                additional = val + res
            elif res > 1:
                additional = res 
            maxrv = max(maxrv, val ** s * additional)
            if val >= 2:
                maxrv = max(maxrv,  s ** val * additional)
            # print(s, val, res, additional, val ** s * additional)

        return maxrv 

执行用时：44 ms, 在所有 Python3 提交中击败了63.47%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了41.18%的用户

failed version

没想到直接遍历所有等分可能，还是会出错。缺少这一步：

if val >= 2:
    maxrv = max(maxrv,  s ** val * additional)

也是神奇，按切分份数来分： 8切分2，3，4份，分别是4 2， 2 3 2， 2 4, 愣是没有3 2 2. 因此才需要上面额外一步。

class Solution:
    def integerBreak(self, n: int) -> int:
        # 还是上暴力法吧 

        maxrv = 0
        split_start = 2
        split_end = max(split_start, n ) # n = 2/3的时候，就靠这个
        for s in range(split_start, split_end + 1):
            val, res = divmod(n, s)
            additional = 1 
            if res == 1:
                s -= 1
                additional = val + res
            elif res > 1:
                additional = res 
            maxrv = max(maxrv, val ** s * additional)
            # print(s, val, res, additional, val ** s * additional)

        return maxrv 

8的最大值为 3 3 2, 但是按切分法，切分2份为 4 4，切分3份为 2 ** 3 2,就是没有 3 * 2 2

输入：8
输出：16
预期结果：18

官方解法与证明

https://leetcode-cn.com/problems/integer-break/solution/zheng-shu-chai-fen-by-leetcode-solution/

最后就是尽可能的分3，剩下的按1/2/3来补。

https://leetcode-cn.com/problems/integer-break/solution/343-zheng-shu-chai-fen-tan-xin-by-jyd/

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1 
        if n == 3:
            return 2 
        power, res = divmod(n, 3)
        additional = 1 
        if res == 1:
            power -= 1 
            additional = 4
        if res == 2:
            additional = res 
        return 3 ** power * additional

执行用时：44 ms, 在所有 Python3 提交中击败了63.47%的用户
内存消耗：13.6 MB, 在所有 Python3 提交中击败了64.71%的用户