# Leetcode 343. Integer Break

## 題解

### DP

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        output = 0
        for num in range(4, n+1):
            sub_ans = 0
            for sub_num in range(1, num // 2 + 1): # n = 10 -> [0, 1, 2, 3, 4, 6, 9, 12, 18, 27, 36] 相當於模擬左右指針窮舉
                sub_ans = max(sub_ans, dp[sub_num] * dp[num - sub_num])
            dp[num] = sub_ans
        print(dp)
        return dp[-1]