【ITニュース解説】Take / Not Take – Part 2: Optimizing Recursion with Memoization and DP

プログラミングの世界には、何かを選択する場面が数多く登場する。その中でも特に重要で強力なパターンが「Take / Not Take」（取るか、取らないか）という考え方だ。これは、現在の要素を問題の解に「含める（Take）」か、あるいは「含めない（Not Take）」かという二択を繰り返しながら、すべての可能性を探索し、最終的な解を見つけ出す手法である。この選択のプロセスを視覚化すると、まるで木の枝が分かれていくように見えるため、「再帰ツリー」と呼ばれる。例えば、コイン両替問題では、ある金額を作るために必要な最小のコイン数を求める際、手持ちのコインを「使う」か「使わない」かを各コインについて判断していくといった具合である。

しかし、この純粋な「Take / Not Take」に基づく再帰的なアプローチは、計算量が指数関数的に増大するという大きな問題がある。これは、同じ計算を何度も何度も繰り返してしまうためで、問題の規模が少し大きくなっただけで、計算に途方もない時間がかかってしまう。コイン両替の例で言えば、効率的な工夫をしないと、計算はO(2^n)という指数関数的な複雑さになり、実用的ではない。

この非効率性を解決するための最初の、そして非常に効果的な手法が「メモ化（Memoization）」である。メモ化とは、一度計算した部分問題の結果を記憶しておき、次に同じ部分問題に出会ったときに、計算し直すのではなく、記憶しておいた結果を直接利用する手法だ。これにより、同じ計算を繰り返す無駄を省き、計算時間を劇的に短縮できる。

コイン両替のメモ化を用いた実装では、memoという二次元配列を使って、特定のインデックス（現在扱っているコインの種類）と残り金額の組み合わせに対する最小のコイン数を記憶する。再帰関数が呼ばれるたびに、まずmemo[idx][left]（インデックスidxまでのコインを使って残り金額leftを作る場合の解）に値が格納されているかを確認する。もし格納されていれば、その値をすぐに返し、そうでなければ計算を実行し、その結果をmemo配列に格納してから返す。この単純な工夫だけで、計算量は指数関数的なものから、問題の「状態」（インデックスと残り金額の組み合わせ）の数に応じた多項式時間（例：O(n × amount)）へと劇的に改善される。

メモ化と似た考え方で、さらに異なるアプローチが「ボトムアップ動的計画法（Bottom-Up Dynamic Programming）」である。これは「テーブル化（Tabulation）」とも呼ばれる。メモ化が「上から下へ（トップダウン）再帰的に解きながら記憶していく」のに対し、ボトムアップDPは「一番小さな部分問題から順に解決し、その結果を積み重ねて最終的な解を導き出す」というアプローチを取る。つまり、再帰を使わず、繰り返し処理でテーブル（配列）を埋めていくことで問題を解く。

コイン両替のボトムアップDPの例では、dpという一次元配列を作成し、dp[i]が「合計金額iを作るのに必要な最小のコイン数」を表すように定義する。まず、金額0を作るには0枚のコインが必要なのでdp[0] = 0と初期設定し、それ以外の金額は非常に大きな値（まだ作れないことを示す）で埋めておく。次に、利用できる各コインについてループを回し、各金額iについて、そのコインを使ってiを作る場合と使わない場合を比較し、より少ないコイン数で達成できる方をdp[i]に格納していく。具体的には、dp[i] = Math.min(dp[i], dp[i - coin] + 1)という式を用いる。これは「現在のdp[i]の値（そのコインを使わない場合や、別のコインを使った場合の最小値）と、現在のコインを使ってiを作る場合のコイン数（i - coinの金額を既に作っていて、そこに現在のコインを1枚加える）を比較して、小さい方を採用する」という意味である。この方法では、再帰の深さによるスタックオーバーフローの心配がなく、しばしばメモ化よりも効率的なコードとなることが多い。

「Take / Not Take」パターンは、コイン両替以外にも多くの問題に応用できる。その代表的な例の一つが「最長増加部分列（Longest Increasing Subsequence, LIS）」問題である。これは、与えられた数列の中から、要素が徐々に大きくなる部分列のうち、最も長いものの長さを見つける問題だ。ここでも、現在の数字を「部分列に含める（Take）」か「含めない（Not Take）」かという選択を繰り返すことで解を導き出す。メモ化を使ったトップダウンのアプローチでは、再帰的に探索しながら、すでに計算した状態（現在のインデックスと直前の要素のインデックス）の結果をmemo配列に記憶する。一方、ボトムアップDPでは、dp[i]を「インデックスiで終わる最長増加部分列の長さ」と定義し、小さなiから順にdp配列を埋めていく。現在のnums[i]より小さいnums[j]があれば、dp[j]+1（nums[j]で終わるLISにnums[i]を追加する）と比較してdp[i]を更新することで、最適な解を構築していく。

これらの問題に共通しているのは、「Take / Not Take」という意思決定の構造と、それによって生じる重複する部分問題をいかに効率的に処理するか、という点である。メモ化は、再帰と組み合わせることで指数関数的な計算量を多項式時間に改善する強力な手法である。一方、ボトムアップDPは、繰り返し処理を通じて小さな問題から順に解き進めることで、よりクリーンで効率的な解決策を提供し、再帰の深さによる制約も回避できる。どちらの手法でも、問題を完全に定義する「状態変数」（例：現在の要素のインデックス、残りの金額、直前の要素のインデックスなど）を正確に特定することが、成功の鍵となる。

「Take / Not Take」パターンは、プログラミングにおける多くの選択問題を解決するための普遍的な思考法だ。純粋な再帰は概念が分かりやすいが、効率が悪いという欠点がある。それを克服するために、メモ化は再帰の欠点を補い、動的計画法はさらに効率的で安定したコードを記述する道筋を示す。これらの技術を習得することは、0/1ナップサック問題、単語分割問題、組み合わせの合計など、より複雑な問題に効率的に対処するための重要なステップとなるだろう。