変更を加える：動的プログラミング

Question

先ほどの講演では、変更の問題を解決するために欲張りな方法を使用することは必ずしも機能しないと言われました。

は、我々はn = 14に到達したい、と我々は異なる値の3枚のコインがあります：d1 = 1、d2 = 7、d3 = 10を次のように

本の例が与えられました。

欲張りのアプローチを使用すると、10 + 1 + 1 + 1 + 1（5コイン）になります。

ダイナミックな問題のアプローチでは、これを正確に解決できると言われました。私はそれを作業しようとしたが、それは戻って5

に来た。これは、これは明らかに行うことができたとき、私たちは5枚のコインが必要であることを改めて示したFが

量を作るために必要なコインの数を保持している

F[14] = min {F[14 – 1] , F[14 – 7], F[14 – 10]} + 1 

     = F[14 – 10] + 1 = 4 + 1 = 5 

を想定します2コイン（7 + 7）を使用します。

何がありますか？ありがとう。

Answer 1

そうでない場合はmin {F[14 – 1] , F[14 – 7], F[14 – 10]}=F[14-10]とします。最小値は実際F[14-7]=1であるため最適では[14] =分2