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.
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..
(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 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]