Problem statement

https://binarysearch.com/problems/Split-Product/

Solution

Equal to Leetcode 0343. Integer Break.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, n):
        def dp(n):
            return n if n < 5 else dp(n-3)*3
        
        if n <= 3: return n - 1
        if n == 4: return n
        return dp(n)