Sumsets (POJ 2229)

This problem is the same as counting how many ways there is to sum up to some money value by given coins face values and count. The data range in this problem is not large, so we can come up a $O(N^2)$ problem. As each number can be used unlimited times, we can give the following recursion formular:

$$DP[i] = \sum_{j = 1}^{j\times j \le i} DP[i - j\times j],$$

Where $DP[i]$ is the number of ways to sum to $i$, our final answer will be $DP[N]$.

import java.io.*;
import java.util.*;

public class Sumsets {
    static private int MOD = 1000000000;
    static private int[] array = new int[1000010];
    private static void solve(int N) {
        for (int i = 0; i <= N; i++) array[i] = 1;
        for (int i = 2; i <= N; i <<= 1) {
            for (int j = i; j <= N; j++) {
                array[j] = (array[j] + array[j - i]) % MOD;
            }
        }
        System.out.println(array[N]);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        solve(N);
    }
}