Python Top-Down and Bottom-Up O(n^2) with Explanation


  • 0
    H

    Given any number that is larger than one, it can be broken down into a pair, and possibly further.
    We have already solved the subproblem if a number is to be broken down further, so we just need to use the max of ((i-j)j and i * i-jdp[j]), with dp[j] representing the optimal solution if we were to break down a number J.

    Example:
    Given n = 7,
    We need to make the comparisons between the following:
    (1, 6), (2, 5), (3, 4)
    For each of these pairs, we can choose to further break down the number into triplets..
    I.E
    (1, 5, 1), (1, 4, 1), (1, 3, 2), (1, 2, 3) and so forth, but we've already solved for those subproblems

    class Solution(object):
        cache = dict()
        def integerBreak(self, n):
            if n in self.cache:
                return self.cache[n]
            if n==1:
                return 1
            max_num = float("-inf")
            for i in range(1, n):
                max_num = max(max_num, i*(n-i), i*self.integerBreak(n-i))
            self.cache[n] = max_num
            return self.cache[n]
    
    class Solution(object):
        def integerBreak(self, n):
            if n == 1:
                return n
                
            dp = [-1 for i in range(n+1)]
            dp[1] = 1
            for i in range(2, len(dp)):
                max_num = float("-inf")
                for j in range(1, i):
                    max_num = max(max_num, (i-j)*j, (i-j)*dp[j])
                dp[i] = max_num
            #print(dp[1:])
            return dp[-1]
    

Log in to reply
 

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