JavaScriptで理解する動的計画法（DP）の基本と2つのアプローチ

動的計画法（Dynamic Programming）とは

動的計画法（DP）は、一つの大きな問題を、より小さな部分問題へと段階的に分解していくアルゴリズム設計手法です。ここで重要なのは、各部分問題が互いに独立して解かれるわけではないという点です。小さな部分問題の結果は記憶（保存）しておき、同じような、あるいは重複する部分問題が出てきた際にその結果を再利用します。

このため、動的計画法は「問題を類似した部分問題に分割でき、その結果を再利用できる」ケースに特に有効です。多くの場合、最適化問題（最良の解を求める問題）に対して用いられます。ある部分問題を解く前に、すでに解いた部分問題の結果を確認し、それらを組み合わせることで全体の最適解を導き出します。

動的計画法を適用できる条件

ある問題に動的計画法を適用するには、一般的に次の条件を満たしている必要があります。

• 部分問題への分割が可能： 問題をより小さな、しかも互いに重複する部分問題に分割できること。
• 最適部分構造： 小さな部分問題の最適解を組み合わせることで、元の問題の最適解が得られること。
• メモ化の利用： 動的計画法では、一度計算した結果を記憶しておく仕組み（メモ化）を活用します。

動的計画法の2つのアプローチ

動的計画法の問題は、大きく分けて次の2つのアプローチで解くことができます。

1. ボトムアップ方式（Bottom-Up）

まず問題を分析し、部分問題をどの順序で解けばよいかを見極めます。最も単純な（自明な）部分問題から解き始め、それを積み上げていく形で、最終的に与えられた元の問題の解へと到達します。この方式は一般に「タブラレーション」とも呼ばれ、反復処理（ループ）を用いて実装されるのが特徴です。

2. トップダウン方式（Top-Down）

与えられた問題を分解しながら解いていく方式です。再帰的に問題を細分化し、途中で「この部分問題はすでに解いた」と気づいた場合は、新たに計算し直さず、保存しておいた解をそのまま返します。この方式は「メモ化再帰」と呼ばれることもあります。

JavaScriptでのシンプルな例：フィボナッチ数列

動的計画法の効果が分かりやすい例として、フィボナッチ数列を挙げます。素朴な再帰実装では同じ値を何度も計算してしまいますが、動的計画法を取り入れることで大幅に効率化できます。

// ボトムアップ方式（タブラレーション）
function fibDP(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

// トップダウン方式（メモ化再帰）
const memo = {};
function fibMemo(n) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  return (memo[n] = fibMemo(n - 1) + fibMemo(n - 2));
}

このように動的計画法を活用すると、指数関数的な時間計算量となる処理を線形時間 O(n) まで改善できるなど、パフォーマンス面で大きなメリットが得られます。フィボナッチ数列以外にも、最短経路問題やナップサック問題など、さまざまな場面で応用されています。