私は、これを説明している論説とブログのトンがあることを知っていますが、私が立ち往生している共通点が1つあります。以下に示す再帰考慮コイン変更アルゴリズムでは再帰はどのように展開されますか？
：
coin_change(coins,i,N) = coin_change(coins,i-1,N) + coin_change(coins,i-1,N-val[i])
は今、これは私たちはコインを除外したり、我々はそれを含めると合計を残りのための問題を解決するためのどちらかと言うと思いますどのかなり簡単そうです。
しかし私の疑問は、無限のコインの供給があるため、できるだけ多くのコインを払うことができるからです。そのことを再帰的解決法にどのように組み入れていますか？
また、この問題の根本的な原因を理解できません。
これはバイナリツリーを作成します。右側のブランチが同じコインを何度も繰り返して検索し、左側のブランチが他のすべてのコインを検索します。
は、単純な場合を取るN = 3とコイン= {1、2}：{1,2}: 1->1->1 (1,1,1)
{2}: ->2 (1,2)
左側の分岐は次のようになります。
{2}: 2->X (No solution)
{2,1}: 2->X (No solution)
{1} ->1 (2,1)
は、同じ結果を与えるだろう
左手ブランチ：
{1}: 1->1->1 (1,1,1)
注1：あなたは2回目の呼び出しで-1を持つべきではありません。
coin_change(coins,i,N) = coin_change(coins,i-1,N) + coin_change(coins,i,N-val[i])
注2：これは、動的プログラミングではありません。
コインが無限に供給されている場合、所定の条件でコインの名目上の全てを除外することができます。例えば、溶液中のニッケルはもうない。 val配列は、コインの数が限られているという問題が多少複雑である[1,5,10,25...]
注意として見ることができる - 私たちは繰り返される値[1,1,1,5,5,10,10,10,10,10,...]との配列を整理したり[1:3; 5:0; 10:12; ...]名目すべてのコインのカウンタの配列を使用する必要があります。