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

• 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]
``````

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