動的計画法とは

AtCoderのプログラミング問題で「動的計画法」で解ける問題がありました。
初めて動的計画法に触れたので自分なりの理解をメモします。

概要

• 動的計画法（Dynamic Programming）は、プログラミング手法の一つで、最適化問題を解くために用いられる。
• 大きな問題をより小さな部分問題に分割し、部分問題の答えを利用して最終的な答えを構築する
• 最適構造（Optimal Substructure、大きな問題の最適解が部分問題の最適解を含む構造を持つ）であることと、重複部分問題（Overlapping Subproblems、同じ部分問題が何度も現れそれらの計算結果を再利用できる）であることが条件である。
• 基本的な手順は以下の通りです。
  • 問題を小さな部分問題に分割する。
  • 部分問題を解く（通常、末端から始めて解を進める）。
  • 部分問題の解を保存し、再利用する（メモ化またはテーブル化）。
  • 保存された部分問題の解を組み合わせて、最終的な解を構築する。
• フィボナッチ数列の計算やナップサック問題、最長共通部分列問題など、さまざまな問題に適用できる。
• 動的計画法を活用しなかった場合に比べ、計算時間やリソースを大幅に節約することができる。

コードの例

フィボナッチ数列を求める場合のコード

def fibonacci(n):
    # 1. 部分問題の解を保存するためのテーブルを初期化する
    dp = [0] * (n + 1)

    # 2. ベースケースを定義する
    dp[0] = 0
    dp[1] = 1

    # 3. 部分問題を解く（小さい問題から大きい問題へ進む）
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    # 4. 最終的な解を返す
    return dp[n]

n = 10
print("The", n, "th Fibonacci number is:", fibonacci(n))

その他分野での応用例

プログラミング以外の分野でも動的計画法の概念は活用できます。
例えば、chatGPTに動的計画法のような指示を出すことで、アイディアの発散をフレームワーク化できます。