動的計画法

本物のページはこちら→dynamic-programming

概要

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

何を表にすればいい??

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

Topcoderで動的計画法の問題

簡単な順に並べます

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

Dinamic Programming. DPと略される。

概要

単なるキャッシュ付きの再帰。
大きい問題を解く過程で同じ小問題が何度も出てくるような場合に、効果的。
小問題を解いた結果を保存して(キャッシュして)再利用することによって、計算量を削減するのだ。
探索で解けるものを、まとめるという工夫で高速化しただけのもの。

動的計画法で解ける問題かどうかの見抜き方

  • 問題が部分問題から構築できる

うーん、それだけじゃ100%動的計画法で解ける!って言えるの?

効果的なアプローチ

  • まず普通に再帰的な解法で実装してみて、その後キャッシュを追加するようにする。
  • 基本的には可能な限り引数が減るような再帰関数を作る。(これがどんな場合でも正しいとは限らない)
  • なるべく狭い範囲でメモするように工夫する

ただメモさえすればいいってわけじゃない。

List of pages tagged with dynamic-programming:

どんな時に使う?

  • 複数の親を持つ子がいるようなツリーになっちゃった場合

  • 格子になってて、同じ場所を何回か通る可能性がある場合

  • 違う組み合わせだけど、結果の値が同じになるようなものが出るような場合(例:ナップザック問題

参考にした本

サポートサイト Wikidot.com