Manjusaka

10-06 leetcode 0343

链接 343. Integer Break

题目

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

题解

看到最大以及拆分，第一反应就可以往 DP 上靠了

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [-float('inf')] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return int(dp[n])

这题还有个数学解法，我没搞懂，先列一下

class Solution:
    def integerBreak(self, n: int) -> int:
        ret = 1
        x = n
        if x == 2:
            return 1
        if x == 3:
            return 2
        while x > 4:
            ret *= 3
            x -= 3
        return ret * x