0

コイン問題の動的計画法の手法で行列がどのように見えるべきかについて、私は混乱しています。1c、5c、10c、および 25c の金種があり、make-change(10) を呼び出すとします。つまり、10 セントを変更したいのですが、最終的な行列/配列はどのように見えるでしょうか。プログラムの最初に配列を割り当てたいので、これを知る必要があります。ここでコードを探しているわけではありません。

4

2 に答える 2

2

1つの次元が現在計算している合計を示し、もう1つの次元が使用できるコインを示すマトリックスを使用できます。たとえば、最初の行は、1cコインのみを使用して特定の合計を達成する方法の数を示します。 、2行目-1cと5c、3行目-1c、5cと10cなど。

したがって、あなたの例では、次のようになります。

Sum:  0 1 2 3 4 5 6 7 8 9 10
Ways: 1 1 1 1 1 1 1 1 1 1 1   (using only 1c coins - N x 1c)
      1 1 1 1 1 2 2 2 2 2 3   (using 1c and 5c coins - either Nx1c, 1x5c + (N - 5)*1c or 2x5c)
      1 1 1 1 1 2 2 2 2 2 4   (using 1c, 5c and 10c coins - one of the above, or 1x10c)

ただし、実際には行列全体を格納する必要はありません。最後の行で常に十分なはずです。

マトリックスの大部分を取り除くための説明：

1cコインのみを使用して答えを見つけたとします（これはそれほど難しいことではありません）。たとえば、単一の配列に格納されているとしますDP。今、あなたはこの情報を持っていて、1cと5cのコインの答えを知りたいと思っています。

sum = 0 to 10次の不変条件を維持しながら、から続行できます。

  • の答えを計算するとき、0から両端までの各数字sumのエントリは、1cと5cのコインを使用する方法の数を示しています。残りのすべてのエントリ（配列の最後まで）には、1cコインのみを使用した場合の回答が含まれています。DPxsum - 1sumsum

そして、それを維持することは実際には非常に簡単です：あなたがの答えを計算しているときx、あなたは知っています：

  • x1cコインのみを使用する方法の数-これはDP[x]、まだ上書きしていないためです。
  • x少なくとも1つの5cコインを使用する方法の数-DP[x - 5]つまり、5cを削除した後に残っているコインの数（または、場合は0 x - 5 < 0）を取得する方法の数。

次に、これら2つの数値を合計して、結果をに格納できますDP[x]。次に、残りのコインについても同様に続けます。

于 2012-10-02T21:20:02.057 に答える
0

金額をコインのリストにマッピングするハッシュマップだと思います。したがって、次のようになります。

{0 => (),
 1 => (1),
 2 => (1,1),
 3 => (1,1,1),
 ...
 13 => (10,1,1,1)
 ...
}
于 2012-10-02T20:33:13.800 に答える