商品が付いているプログラミングのクイズをやっていたので挑戦した
正解だったけど残念ながら商品はもらえずorz
せっかくやったのでブログ記事にしておく
公開していいのかよくわからないけど、まずかったら消します
問題
2円、3円、5円、……とフィボナッチ数的な価値の硬貨があるときに100万円を支払う方法が何種類あるのかを答える
解法
問題を読んですぐに蟻本で読んだ分割数の問題に似ていると思いました
分割数はある自然数を自然数の和として何通りで表せるか、という問題です
分割数は動的計画法で計算することができます
今回の問題は和を作るときに使える数に制限がある分割数の計算と考えることができます。
同様に動的計画法で計算します。
\(i\)種類目までの硬貨を好きな個数使って\(j\)を表した時の組み合わせの数を\(dp[i][j]\)とします。
\(i\)種類目の硬貨を\(F[i]\)としたとき\(dp[i][j] = dp[i - 1][j] + dp[i][j - F[i]]\)の関係が成り立ちます
これは\(i\)種類目までで\(j\)を表した時の組み合わせの数は、\(i - 1\)種類目まで使った時の組み合わせの数と加えて\(F[i]\)を使った時の組み合わせの数の和であることを表しています。
あとはこれを順に計算していくだけです
ソースコード
M = 1000000 F = [2, 3] while F[-1] + F[-2] <= M: F.append(F[-1] + F[-2]) L = len(F) temp = [0] * (M + 1) dp = [temp[:] for i in xrange(2)] dp[0][0] = 1 for i in xrange(L): for j in xrange(M + 1): dp[1][j] = dp[0][j] if j - F[i] >= 0: dp[1][j] += dp[1][j - F[i]] dp[0] = dp[1] dp[1] = temp[:] print dp[0][-1]
