POJ 3181 - Dollar Dayz

http://poj.org/problem?id=3181

概要

N ドル使って 1ドル, ..., Kドルの商品を買うとき，買い方が何通りあるか答える．

制約

• 1 <= N <= 1000
• 1 <= K <= 100

解法

dp[n][k] := n ドルで 1ドル, ..., kドルの商品を買うときの買い方

で DP．

dp[n][0] を 1 として，

dp[n][k] = Σdp[n-i][i]

で更新する．

最大ケース dp[1000][100] の値は unsigned long long にも収まらないので多倍長計算が必要．

 1 import java.util.*;
 2 import java.math.*;
 3 import java.io.*;
 4 
 5 public class Main {
 6   public static void main(String[] args) {
 7     Scanner cin = new Scanner(System.in);
 8     int N = cin.nextInt();
 9     int K = cin.nextInt();
10     BigInteger[][] dp = new BigInteger[N+1][K+1];
11     for (int k = 0; k <= K; k++) {
12       dp[0][k] = BigInteger.ONE;
13     }
14     for (int n = 1; n <= N; n++) {
15       for (int k = 1; k <= K; k++) {
16         dp[n][k] = BigInteger.ZERO;
17         for (int i = 1; i <= k && n-i >= 0; i++) {
18           dp[n][k] = dp[n][k].add(dp[n-i][i]);
19         }
20       }
21     }
22     System.out.println(dp[N][K]);
23   }
24 }