9 lines Python DP


  • 0
    class Solution(object):
        def integerBreak(self, n):
            if n<=3:
                return n-1
            dp_lis = [2, 3]  # special cases that integerBreak(n)<n, when multiply we set them to n
            while len(dp_lis)<n-1:
                max_multi = 0
                for i in range(1, len(dp_lis)/2+1):
                    max_multi = max(max_multi, dp_lis[i-1]*dp_lis[-i-1])
                dp_lis.append(max_multi)
            return dp_lis[n-2]
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.