トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

動的計画法

[アルゴリズム,DP]

練習のための問題は 競技プログラミングの履歴

動的計画法

英語でDynamic Programming

  動的計画法とメモ化

   動的計画法とメモ化の違いについての考察結果を書いておきます。
   
   動的計画法(dynamic programming)は、問題を部分問題に分割しながら処理を行なう際に、
   一度行なった部分問題の計算結果を表に保存することにより、効率的な処理を実現する方法一般を指す言葉です。
   
   一方、メモ化(memoization)は、プログラムコードの中で、関数の計算の結果を保存しておき、
   同じ引数による関数呼び出しがあった場合は、保存した結果を返すというものです。
   造語のmemoization自体は1968年から存在するようです。
   
   この2つの違いを述べると、動的計画法は、アルゴリズムを工夫することにより、
   過去の計算結果を表に保存し問題を高速に解く手法を広くカバーする「概念」で、メモ化というのは、
   実装レベルで過去の計算結果を再利用して高速化する「実現手法」のひとつという説明で良いように思います。

  今把握している動的計画法のアルゴリズム一覧

 確かに DP のバリエーションは非常に多岐にわたるのですが、そのほとんどが以下の 3 つのフレームワークで説明できると思います:
 
 ・ナップサック DP
 ・区間 DP
 ・bit DP

というわけで、このページでもDP(=動的計画法)を3つに大別してみる。すべてを把握しにくいので、仮決めで名前だけ入れている部分あり。

 世の中のDPの問題というのは、大抵次のように分類できます。
 
 ・最短経路DP
 ・最長経路DP
 ・経路総数DP
 ・確率DP (例: AOJ1277: Minimal Backgammon)
 ・期待値DP (例: AOJ2236: スプリング・タイル)
 ・ゲームDP (例: AOJ1230: Nim)

これはデータの持つ性質というより、問題の傾向からの分類に見えます。ただし、動的計画法自体をDAGというグラフ理論的なものの見方で解いているのは、本質を見抜いている感じがします。

う〜ん、これもうわかんねえな、お前どう?

とりあえず解けたらいいのです

ナップサック DP

名称 Wikipedia
最大和問題
動的計画法 - コイン問題
動的計画法 - ナップサック問題 Wikipedia - ナップサック問題
レーベンシュタイン距離 Wikipedia - レーベンシュタイン距離

区間 DP

名称 Wikipedia

bit DP

名称 Wikipedia

未分類

  このWikiの関連するページ

  • 英語から翻訳
    • GeeksforGeeks(部分行列)?
お名前: コメント: