◉ 動的計画法
Kyopro Encyclopedia of Algorithms

これはステージング環境です。5 秒後に自動的に本番環境 (https://noshi91.github.io/algorithm-encyclopedia) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /algorithm-encyclopedia/dynamic-programming#noredirect を利用してください。
name
動的計画法
short description
動的計画法とは、アルゴリズムの分類のひとつ。対象となる問題を複数の部分問題に分割して、部分問題の答えを記録しながらそのすべてを解くという形のアルゴリズムの総称である。動的計画法に分類されるようなアルゴリズムの実装方法の典型例として、配列をループで埋めていく実装や、メモ化を伴なう再帰による実装がある。

概要

動的計画法 (dynamic programming; DP) はアルゴリズムの分類のひとつである。対象となる問題を複数の部分問題に分割し、部分問題の答えを記録しながらそのすべてを解くという形のアルゴリズムたちを総称して動的計画法と呼ぶ。

分類

動的計画法に分類されるアルゴリズムたちは、さらに細かく分類することができる。また、そのような分類方法もまたいくつかに分類できる。

状態にもとづく分類

値にもとづく分類

漸化式や実装方法にもとづく分類

関数の再帰的定義による理解

再帰的に定義された関数 $f : X \to Y$ をその定義に従って計算するとき、それぞれの $x \in X$ について $y = f(x)$ を記憶しておきちょうど一度のみ計算するようにすれば指数的な爆発を防げ、$O(\vert X \vert)$ 回の漸化式の計算で値が求まる。動的計画法とはこのような事実を利用したアルゴリズムのことである、という見方ができる6。 このとき $X$ は状態の集合であり $Y$ は値の集合である。

ループとメモ化再帰

動的計画法に分類されるようなアルゴリズムの実装方法の典型例として、配列をループで埋めていく実装や、メモ化を伴なう再帰による実装がある。 ただし、競技プログラミングの界隈においては、特に配列をループで埋めていく実装のみを指して動的計画法と呼ばれることもある7。

配る DP と貰う DP

ほとんどの場合、DP はその漸化式をどのように実装するかによって、貰う DP か配る DP のどちらかに分類できる。

$y = f(x_0, x_1, x_2, \dots)$ という形で書かれた漸化式をそのまま用いるのが貰う DP である。 貰う DP の特徴としては、in-place DP などの形の高速化がしやすいことが挙げられる。

$y = f(x_0, x_1, x_2, \dots)$ という形で書かれた元々の漸化式を逆転させて、$x_0, x_1, x_2, \dots$ のそれぞれを主体として $y \gets g(y, x_0); y \gets g(y, x_1); y \gets g(y, x_2); \dots$ のような更新を行うことで $y$ を計算するのが配る DP である。 配る DP の特徴としては、遷移関係と処理の向きが一致しており考えやすいことや、添字に負数がでてきにくく実装しやすいことが挙げられる。

その他

関連項目

外部リンク

注釈

  1. uwi によるツイート https://twitter.com/uwitenpen/status/1229100036450996224archive.org ↩

  2. https://twitter.com/shojin_comp/status/1229099045475344384archive.org ↩

  3. kort0n によるツイート https://twitter.com/kyort0n/status/1229096380431396864archive.org ↩

  4. snuke によるツイート https://twitter.com/snuke_/status/928314561890959360archive.org ↩

  5. yosupo によるツイート https://twitter.com/yosupot/status/928313911891214336archive.org ↩

  6. kimiyuki による記事 DPそのものとは何であるかを理解する - うさぎ小屋archive.org ↩

  7. chokudai によるツイート https://twitter.com/chokudai/status/1010049288460570624archive.org ↩

  8. furuya1223 によるツイート https://twitter.com/furuya1223/status/1189903074107654145archive.org ↩

  9. kuuso によるツイート https://twitter.com/kuuso1/status/1189904707067600901archive.org ↩

  10. tempura0224 によるツイート https://twitter.com/tempura_cpp/status/1177147483010387968archive.org ↩

  11. kanra824 によるツイート https://twitter.com/Md19970824/status/1254015456362459137archive.org ↩

  12. 例題: https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_e ↩ ↩2

  13. sky58 によるツイート https://twitter.com/skyaozora/status/1177173768738705408archive.org ↩

View full history / Report issues / Edit this page
changelog
  • 2021年02月23日「記事作成」 authors: kimiyuki, reviewers: noshi91
license
Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.