# Dollar Dayz (POJ 3181)

A simple problem, it is in fact equal to how many ways we can use several type of coins to spend a given sum of money. Every coins has unlimited numbers.

Our original DP formular is:

While is the number of ways to spend with first types of coin. But we can do it better to reduction the formular to:

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

public class DollarDayz {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt(), K = in.nextInt();
BigInteger[] dp = new BigInteger[N + 1];
dp[0] = new BigInteger("1");
for (int i = 1; i <= N; i++) {
dp[i] = new BigInteger("0");
}
for (int k = 1; k <= K; k++) {
for (int i = k; i <= N; i++) {