# Dynamic Programming – Integer Break

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. For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

We can useDynamic Programming (DP) to solve this problem. The puzzle does not ask you exactly how to break the integer. If we use f(n) to denote that the maximum product to break the integer n, then we have the following recurrence formula:

for

.

If we break the integer i-j, the intermediate result is f(i-j) otherwise we have to check if we break i into i-j and j. The time complexity is O(n^2) and the space complexity is O(n).

`class Solution { public:     int integerBreak(int n) {         vector<int> f(n + 1, 0);         f[1] = 0;         f[2] = 1;         for (int i = 2; i < n + 1; i ++) {             for (int j = 1; j < i; j ++) {                 f[i] = max(f[i], max(i - j, f[i - j]) * j);             }         }         return f[n];     } };`
`class Solution { public:     int integerBreak(int n) {         vector<int> f(n + 1, 0);         f[1] = 0;         f[2] = 1;         for (int i = 2; i < n + 1; i ++) {             for (int j = 1; j < i; j ++) {                 f[i] = max(f[i], max(i - j, f[i - j]) * j);             }         }         return f[n];     } };`

–EOF–

GD Star Rating