Python solution with detailed explanation


  • 0
    G

    Solution

    Integer Break https://leetcode.com/problems/integer-break/?tab=Description

    Dynamic Programming

    • Update equation: dp[i] = max(dp[i], max(dp[complement], complement) * j)
    class Solution(object):
        def integerBreak(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n == 1:
                return 1
            dp = [0]*(n+1)
            for i in range(2, n+1):
                for j in range(1, i):
                    complement = i-j
                    dp[i] = max(dp[i], max(dp[complement], complement)*j)
            return dp[-1]
    

Log in to reply
 

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