蟻本の練習問題埋め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部分は超単純だけど、多倍長を使う必要がある…