動的計画法の仕組み

動的計画法は、小さい部分問題の答えを表に記録しておき、それを使い回しながら大きい問題の答えを求める方法です。この例では、硬貨1・3・4を使う最小枚数問題を題材に、金額0から順に、その金額を作る最小枚数を表に記録していきます。すでに計算した小さい金額の答えを使い回すため、貪欲法と違って必ず最適な答えにたどり着きます。