LC 0343 [M] Integer Break - ALawliet/algorithms GitHub Wiki

class Solution:
    def integerBreak2(self, n: int) -> int:
        # O(n^2), O(n)
        @cache
        def dfs(num):
            if n == 1:
                return 1
            
            res = 0 if num == n else num
            for i in range(1, num):
                val = dfs(i) * dfs(num - i)
                res = max(res, val)
            return res
        
        return dfs(n)

    def integerBreak(self, n: int) -> int:
        # O(n^2), O(n)
        dp = { 1 : 1 }
        for num in range(2, n + 1):
            dp[num] = 0 if num == n else num
            for i in range(1, num):
                val = dp[i] * dp[num - i]
                dp[num] = max(dp[num], val)
        return dp[n]