343. Integer Break
Difficulty: Medium
Topics: Math, Dynamic Programming
Similar Questions:
Problem:
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
</div> </div>Solutions:
class Solution {
public:
int integerBreak(int n) {
unordered_map<int, int> cache;
if (n == 2) return 1;
if (n == 3) return 2;
return helper(n, cache);
}
private:
int helper(int n, unordered_map<int, int>& cache) {
if (cache.count(n) > 0) return cache[n];
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 3;
int prod1 = 2 * helper(n - 2, cache);
int prod2 = 3 * helper(n - 3, cache);
int ret = max(prod1, prod2);
cache[n] = ret;
return ret;
}
};