2023.10.06 Today's Challenge

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

LeetCode - The World's Leading Online Programming Learning Platform

dp로 푸는 문제. 이제 몇 일 동안은 dp 만 나올 듯.

class Solution:
    def integerBreak(self, n: int) -> int:
        @cache
        def dp(num):
            if num <= 3:
                return num
            
            ans = num

            for i in range(2, num):
                ans = max(ans, i * dp(num-i))
            
            return ans

        if n <= 3:
            return n - 1
        
        return dp(n)