343. Integer Break

Python

Top-Down DP

from math import inf
from functools import cache


class Solution:
    def integerBreak(self, n: int) -> int:
        @cache
        def dp(k):
            if k == 1:
                return 1

            result = -inf
            for i in range(1, k):
                result = max(result, i * dp(k-i), i*(k-i))
            return result
        return dp(n)

3s

• Time: O(logN), Space: O(1), 算比較快的解法

• 乍看之下沒有規則，但把n<10拆完會發現規律

  • 因為2*2 > 1*3，盡可能將4分解成2*2

• 參考

n	breaks	memo
2	1+1
3	1+2
4	2+2	不要拆成1+3
5	2+3	以下開始循環
6	3+3
7	3+2+2
8	3+3+2
9	3+3+3
10	3+3+2+2

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1

        pow, remain = divmod(n, 3)

        if remain == 0:
            return 3 ** pow

        if remain == 1:
            return 3 ** (pow-1) * 4

        return 3 ** pow * 2