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]が答えになる。
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]が答えになる。