Project Euler31：プログラムソリューションの理解

Question

私は解決策を理解しようとしています プロジェクトオイラー＃31 フォーラムで見つけました。

問題は、次の値でコインが与えられることです。

coins=[1,2,5,10,20,50,100,200]

私たちは、200に到達する可能性のあるすべての方法を生成することを任されています。たとえば、10*10+100 = 200は1つの可能な方法です。

1. 質問2：以下のコードはどのように機能しますか！私のアプローチに比べて非常にエレガントでシンプルで簡単に見え、より速く実行されます。

フォーラムを閲覧していたので、この解決策を見つけました。

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

最初の行は、コイン値のリストにすぎません。 2番目の行は、1を持つアレイを作成し、その後200 0が続きます。しかし、次の4行で私は混乱しました。配列内の可能な方法の数を増やしていると思うので、Case_num [200]はリストの最後のエントリを提供しますが、それがどのように機能するかはわかりません。

Answer 1

あなたが言ったように、これはとても素晴らしい解決策です。コードは、各コインの宗派を伴う1〜200の各繰り返しを通じてそれ自体に基づいています。

case_num配列は、最初は[1、0、0、0、0、0、0、0、0]で構成されています。

これらの数値（最初の1以外の）は、これまでに繰り返したP_LISTのコインを使用して、指定された合計（数のインデックスで表される）まで構築できる方法の数です。

P_LISTの最初のコインは1です。したがって、1がインデックス内に収まる場合、前のインデックスで値を取得し、現在のインデックスに追加します。これは、25に到達するための5つの既知の方法があり、サイズ1のコインを見つけたばかりである場合、26に到達するための5つの方法もあります。 。

したがって、1を繰り返した後、[1、1、1、1、1 ... 1、1]になります。

これで、コインで上に移動します。今回は2のコインを使用しています。プロセスをさらに1時間歩きましょう。 2がインデックスよりも少ない場合、現在のインデックスの前のインデックスにアクセスする方法の数を追加します。

たとえば、2つはインデックス1内に収まりませんが、インデックス2に収まります。したがって、0から2に到達する新しい方法を作成しただけで、0に到達できるすべての方法を実行して、現在のインデックスに追加します。インデックス27では、インデックス内に2つに適合するので、25に到達して27に追加できる方法の数を取得します（25 + One 2 Coinに到達する方法のすべて） +（すべての方法）サイズ2のコインがあることを知る前に、27に達する必要がありました。

したがって、2を繰り返した後、[1、1、2、2、3、3、4、4]になります。

あなたがまだ問題を抱えているなら、プログラム全体を試してみようとする価値があるかもしれません（おそらく200ではなく50のように減少したかもしれません）。