動的計画法

dynamic-programming.png

概要

  • まとめられる処理をまとめて、同じ計算を行わないようにする
  • 大きい問題を解く過程で同じ小問題が何度も出てくるような場合に、小問題を解いた結果を保存しておいて再利用することで計算量を削減する方法[2]

何を表にすればいい??

ありうるすべての組み合わせを表(2次元配列)にする

Topcoderで動的計画法の問題

簡単な順に並べます

  • SuperSum…..漸化式の値を求めるような問題
Bibliography
2. データ構造とアルゴリズム (新・情報 通信システム工学….大学の教科書としても使われている。難しかった。結構図があっていい。

combination

サポートサイト Wikidot.com combination