Yesterday I met a problem called "divide integer". Unfortunately, I failed to solve it despite my half-hous' thought. So I summary the solution of this problem here to enhance my comprehension.

The Problem

A positive integer n could be divided into the sum of many integers, which are n1+n2+...+nk, n1>=n2>=...>=nk, k>=1.

Now given a positive integer n, please tell how many ways there are to divide it and please mod the result by 10^9+7 since it may be a very large number.

The range of the data: 1<=n<=1000.

Algorithm A: Conversion to Complete Knapsack Problem

"When you find it hard to construct a state transition equation, try to compare it with other known problems and think if it can be converted to another problem." This what this problem and this solution told me.

Now let's see the problem again, integer n is divided into many integers which are smaller than or equal to n. In other words, we should use many integers in range n to make them sum to n.

We can give these integers a meaning: weight. They could be regarded as many items with weight 1~n and the count of each item is infinite. Our task is to use them to exactly fill our bag, which has capacity n.

Now we start writing our state transition equation. Let f[i][j] to indicate "the number of ways to fill capacity j with the first i items". Then we can get the equation below.

f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2*i] + f[i - 1][j - 3*i] + ...

The time compexity is O(n^2logn), which is still too complex.

Since it's "complete knapsack", we can optimize the equation. We notice that there is a relation between f[i][j] and f[i][j - i].

f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2*i] + f[i - 1][j - 3*i] + ... 
f[i][j - i] =           f[i - 1][j - i] + f[i - 1][j - 2*i] + f[i - 1][j - 3*i] +f[i - 1][j - 4*i] + ...

So the equation could be converted to f[i][j] = f[i - 1][j] + f[i][j - i]. Now the time complexity is O(n^2). In practice, we can further reduce its space complexity by scoll array. The code below is an implemention of it.

#include <iostream>
#include <algorithm>

using namespace std;

static const int N = 1001;
static const int M = 1e9 + 7;
int n;
int f[N];

int main(){
    cin >> n;

    f[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            f[j] = f[j] + f[j - i];
            f[j] = f[j] % M;
        }
    }

    cout << f[n];
}

Algorithm B: Construct State Transition Equation In a Clear Way

In fact, the conversion in Algorithm A is an important method in math, which is "conversion and transformation". However, is there a way to directly solve the problem? The answer is YES!

We could use f[i][j] to indicate the conditions that sum i numbers to j. This is easy to understand but the key is how to construct the state transition equation.

When we think of f[i][j], we can divide this state into two parts, as shown in the picture below.

All the conditions of f[i][j] consists of two parts, which are the numbers without any "1" and the numbers with at least one "1". Obviously, the part with at least one "1" could be described as f[i - 1][j - 1], which means that now there are i - 1 numbers construct number j - 1, and we add a single "1" to all of them, getting a group of conditions that has at least one "1".

What about the other part? Here is the magic! Let group A is a group with i numbers and there sum is j. Now we don't know if there is any "1" in A. However, what if we add each number in A with "1"? All the numbers will be larger than 1 and the sum of them will come to j + i because we add i times totally.

Let's reverse this process. There are originally i numbers in A and there sum is j - i. Then we add "1" to each member of A and we get a group whose sum is j and there are no "1" in the group.

In conclusion, the state transition equation could be expressed as below.

f[i][j] = f[i - 1][j - 1] + f[i][j - i];

And the result is the sum from f[1][n] to f[n][n].

After the optimization of space complexity, the code may like this.

#include <iostream>
#include <algorithm>

using namespace std;

static const int N = 1001;
static const int M = 1e9 + 7;
int n;
int f[N];

int main(){
    cin >> n;

    int r = 0;
    for(int i = 1; i <= n; i++){
        int temp = f[i];
        for(int j = 1; j <= i - 1; j++){
            f[j] = 0;
        }
        f[i] = 1;
        for(int j = i + 1; j <= n; j++){
            int t = f[j];
            f[j] = (temp + f[j - i]) % M;
            temp = t;
        }
        r += f[n];
        r = r % M;
    }

    cout << r;
}

Conclusion

Well, I can't tell which method is better. They are two different ways leading to the same end. The second method is very ingenious but I think learning the first method is more important because it makes us to convert unknown problems to the field we are familiar with.