Coding Exercise – C ++ – Solve Integer Split using Dynamic Programming – 3 Implementation

Question: Given an integer (maximum 100), compute the number of distinct ways to split the number using non-negative integer numbers.

For example, given 5, there are 7 ways to split it.

5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+1+3
5=2+3
5=1+4
5=5

Mathematically,

The order of the numbers does not matter, i.e. 1+4 is the same as 4+1.

Sure, we can use brute-force, but it is the hell too slow for large inputs. We can also use back trace to search the number of different answers (each expanded number is larger or equal to its previous node, and count the answer if sum reaches). This method is good if we want to print all different solutions but it is not efficient if we just want to know the number.

Instead of search algorithms, we can use quicker algorithm based on Dynamic Programming (DP) and some Combinatorial Mathematics.

The above list the solutions, let’s re-group them into five.

5=1+1+1+1+1
5=1+1+1+2=1+2+2
5=1+1+3=2+3
5=1+4
5=5

The first is the solution with every number less or equal to 1.

The second is the solution with every number less or equal to 2.

and so on, you know the pattern.

So, if we define f(n, k) as the answer for splitting number n with numbers no bigger than k, we can have a recurrence formula.

The total number for n is f(n, n). f(0, 1) is set to 1 because for sum=0, we have 0 = 0, which satisfies that each number is no bigger than 1.

With this recurrence formula and the initial boundary values, we can quickly implement using pure recursion method.

1
2
3
4
5
6
7
8
9
10
11

int f(int n, int k) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (k == 1) return 1;
    int s = 0;
    for (int i = 1; i <= k; i ++) {
        // recursion, redundant computation
        s += f(n - i, i);
    }
    return s;
}

int f(int n, int k) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (k == 1) return 1;
    int s = 0;
    for (int i = 1; i <= k; i ++) {
        // recursion, redundant computation
        s += f(n - i, i);
    }
    return s;
}

Note, we should check the given parameter n in case that it is less than 0, otherwise, it will crash (stack overflow) unless checked in the for loop. 

The recursion quickly draws the picture, but it is implementation-inefficient because lots of intermediate values are computed again and again. One improvement is to remember this by storing this in arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>
#include <string.h>
 
using namespace std;
 
const int maxN = 100;
 
int ans[maxN][maxN];
 
int g(int n, int k) {
    if (n < 0) return 0;     
    if (n == 0) return 1;     
    if (k == 1) return 1;     
    // check if f(n, k) has been computed before     
    if (ans[n][k] > 0) return ans[n][k];
    int s = 0;
    for (int i = 1; i <= k; i ++) {
        s += g(n - i, i);
    }
    // save the result
    ans[n][k] = s;
    return s;
}
 
int main() {
    // memset((void*)ans, 0, sizeof(ans)); // not computed set to 0
    for (int i = 1; i <= 10; i ++) {
            cout << g(i, i) << endl;
    }
    return 0;
}

#include <iostream>
#include <string.h>

using namespace std;

const int maxN = 100;

int ans[maxN][maxN];

int g(int n, int k) {
    if (n < 0) return 0;     
    if (n == 0) return 1;     
    if (k == 1) return 1;     
    // check if f(n, k) has been computed before     
    if (ans[n][k] > 0) return ans[n][k];
    int s = 0;
    for (int i = 1; i <= k; i ++) {
        s += g(n - i, i);
    }
    // save the result
    ans[n][k] = s;
    return s;
}

int main() {
    // memset((void*)ans, 0, sizeof(ans)); // not computed set to 0
    for (int i = 1; i <= 10; i ++) {
            cout << g(i, i) << endl;
    }
    return 0;
}

We use a two dimension array ans[][] (static array) to hold the result, if it has not been computed (value = 0), compute the answer and store it. It is worth mentioning that the initialization to such array is that all elements are set to zero, so the following can be omitted.

1

memset((void*)ans, 0, sizeof(ans));

memset((void*)ans, 0, sizeof(ans));

How to convert this iteratively? We change slightly the formula.

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

int h(int n, int k) {
    ans[0][1] = 1;
    for (int i = 1; i <= n; i ++) { // number to split
        for (int j = 1; j <= i; j ++) { // using how many numbers
            for (int a = 1; a <= j; a ++) { // accumulator
                ans[i][j] += ans[i - j][a];
            }
        }
    }
    int c = 0;
    for (int i = 1; i <= n; i ++) {
        c += ans[n][i]; // sum up 
    }
    return c;
}

int h(int n, int k) {
    ans[0][1] = 1;
    for (int i = 1; i <= n; i ++) { // number to split
        for (int j = 1; j <= i; j ++) { // using how many numbers
            for (int a = 1; a <= j; a ++) { // accumulator
                ans[i][j] += ans[i - j][a];
            }
        }
    }
    int c = 0;
    for (int i = 1; i <= n; i ++) {
        c += ans[n][i]; // sum up 
    }
    return c;
}

The f(n, k) denotes the answer of using k numbers to form up the number n. So the total sum is .

All above three algorithms have complexity, but the third implementation is the fastest because no recursion (no stacks are created for each recursive calls). The second one is faster than the first one. The first solution is quick and easy to cook and the second is an improvement (that is easy) to made base on the first one. The third iteration approach is a bit difficult to code.

–EOF (The Ultimate Computing & Technology Blog) —