Dynamic Programming – Integer Break

Dynamic Programming (DP) is one of the very important algorithm in Computer Science. Here is the simplest example of demonstrating the concept of DP if you want to tell you 5-year-old son.

dynamic-programming-interview-questions

Give 5 matches to your son, and ask: “How many matches do you have?”
— The kid counts and says: Five.
Then, give one more match to your son and ask, how about now?
— The kid says Six because he knows Five + One More equals Six…
The concept of DP is quite similar to this: breaking a problem into a smaller one + memorization of solutions to sub-problems.

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 use Dynamic 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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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];
    }
};

We have a better algorithm to compute the maximum split product by breaking an integer: Greedy Algorithm to Maximize the Split Product (Integer Break)

Also: Teaching Kids Programming – Maximum Product by Splitting Integer using Dynamic Programming or Greedy Algorithm

–EOF (The Ultimate Computing & Technology Blog) —