はじめに 動的計画法 ナップサック問題 例題 考え方 実装例 おわりに 参考 はじめに こんにちは.talosです.今回はナップサック問題を例題に,動的計画法を説明します.競技プログラミングとかでもよく使われるので,これから挑戦しようという人は必見です. 動的計画法 動的計画法(DP:Dynamic Programming)は問題を部分問題に分割し,それらを解くことで最終的な解を求める方法です.似たような方法に分割統治法がありますが,これとの違いは部分問題を解いた結果を保存しておくことです.これによって,分割統治法でよくある同じ部分問題を何度も解いてしまうということを避けることができます.言葉…