DP Python Solution

  • 0

    For 10 we can have the following:

    1+9, 2+8, 3+7, 4+6, 5+5

    Since we know we want to maximize the total product, there is overlapping subproblem, as maximizing the product of 9 will help us maximize the total product of 1 * 9.

    Therefore we can derive the recurrence relationship:

    res = max(factor2, dp[factor2]) * max(factor1, dp[factor1])
    def integerBreak(self, n):
        dp = [0 for i in range(n+1)]
        for num in range(2, n+1):
            for addend in range(1, num/2+1):
                res = max(addend, dp[addend]) * max(num-addend, dp[num-addend])
                dp[num] = max(dp[num], res)
        return dp[n]

Log in to reply

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