algorithm - コインの最小数を見つけるための動的計画法

Question

ハードウェアとして持っている質問の一部を理解しようとしていますが、それは本当に中国語のように見えます...

コインがあるとしましょうx_1, x_2, x_3, ... x_n。 x_1 = 1いつも。最小限のコインで一定の金額を提供したいと考えています。次に、動的計画法を使用します。

そして今、私はこれを理解していません - amount を返すコインの最小量はc(i,j) = min { c(i-1,j), 1+c(i,j-x_i) } どこですか。c(i,j)j

Answer 1

c(i,j-x_i)j-x_iは、コインのみを使用して値を取得するためのコインの最小数ですi,i+1,...,n(これは誘導仮説であり、再帰式が保証するものです)。
したがって、与えられたコインのセット + と評価された追加のコイン1+c(i,j-x_i)を取得するための最小限の方法であり、これを使用することにしました。j-x_ix_i

これから、c(i,j) = min { c(i-1,j), 1+c(i,j-x_i) }実際に「何が最善か」を徹底的に選択しています。

1. 現在のコインを取得し、残りの小さな問題を再帰的にチェックする
2. それを取らないことを決定し、もう一度、より小さな問題を再帰的にチェックします。

それらを最小限に抑えることで、（すべての可能性に対して徹底的に行われるため）最小になることが保証されc(i,j)ます。