蟻本の練習問題埋め2-3(2)

DP(漸化式を工夫して高速化する問題)

POJ 1742 - Coins

http://poj.org/problem?id=1742
蟻本P62の個数制限付部分和問題とだいたい同じ

POJ 3046 - Ant Counting

http://poj.org/problem?id=3046
蟻本P67の重複組み合わせとだいたい同じ

POJ 3181 - Dollar Dayz

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

問題

1~Kドルの商品があるとき、ちょうどNドル使って購入できる商品の集合は何通りあるか。
同じ値段の商品を何個選んでも良い。

制約

N<=1000
K<=100

解法

dp[i][j] = 1~iドルの商品まで使ったとき、計jドルになる商品の集合の総数
蟻本P58の個数制限なしナップサック問題のような感じでO(NK)。
DP部分は超単純だけど、多倍長を使う必要がある…