project euler 31

問題

1,2,5,10,20,50,100,200のコインが無数にある。
このコインを使って、200を作る組み合わせは何通りあるか。

考え方

dp[i]:=iを作る組み合わせのかず
とすると、小さいコインから順番に、コインpを使うと、
dp[i+p] += dp[i]
とできる。(dp[0]=1として、0<=i<=200)

すべてのコインについて上記を繰り返したとき、dp[200]が答えになる。