ナップサック、コイン問題 考え方

考え方のイメージ
ナップサック問題
荷物の詰まった袋がある。そこから次に入れたい荷物の分だけ減らして、そこに新しい荷物を入れたとする。入れる前の価値と入れた後の価値を比較して、新しい荷物を入れた後の方が価値が高ければ新しい荷物を実際に入れて、かわらないもしくは低い場合はそのまま。

コイン問題
指定されたコインの金額で作った合計金額から次に使用する予定のコインの金額を引く。そこに新しいコインを追加する。追加する前と後でコインの枚数が少なくなったら採用、かわらないもしくは多くなった場合は不採用。

なんで速くなるのかは考え方のイメージとは別問題。
dpで速くなるのは計算済みの結果を再利用するので同じ計算をしないから。