January 2006 Problem 'ddayz' Analysis

by Bruce Merry

This is a fairly straightforward dynamic programming problem. Let f(T, C) be the number of ways to create a total of T with coins 1, 2, ..., C. Then f can be expressed with the following recurrences:

f(0, 0) = 1
f(T, 0) = 0 for T > 0
f(T, C) = f(T, C - 1) for T < C
f(T, C) = f(T, C - 1) + f(T - C, C) for T >= C

If an outer loop is placed over C, it can be seen that we only need to keep one row of the DP table at a time.

One catch is that the answer might be extremely large, so it is necessary to use a BigInteger class (either use java.math.BigInteger or write your own if you don't use Java).

Rob adds: Don't fear writing bigint addition; it takes just a few minutes. Requiring knowledge of when to use bigints is a favorite little trick on international competitions. It changes a trivial problem up one level to an easy combination problem, but many will miss the requirement. Always estimate the magnitude of your answer in these sorts of problems where successive addition yields an answer.

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

public class ddayz {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader("ddayz.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("ddayz.out")));

        StringTokenizer tok = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(tok.nextToken());
        int K = Integer.parseInt(tok.nextToken());
        in.close();

        BigInteger[] dp = new BigInteger[N + 1];
        dp[0] = BigInteger.ONE;
        for (int i = 1; i &lt;= N; i++)
            dp[i] = BigInteger.ZERO;

        for (int i = 1; i &lt;= K; i++)
            for (int j = i; j &lt;= N; j++)
                dp[j] = dp[j].add(dp[j - i]);

        out.println(dp[N]);
        out.close();
    }
}