【ITニュース解説】Mastering the “Take / Not Take” Pattern in Recursion, Backtracking, and Dynamic Programming

多くのアルゴリズム問題、例えば部分列の特定や組み合わせ最適化といった課題を解決する上で、非常に強力でシンプルな考え方がある。それが「Take / Not Take（取るか、取らないか）」というパターンだ。このパターンを深く理解することは、再帰、バックトラッキング、そして動的計画法（DP）といった重要なアルゴリズムを効率的に習得し、問題を解くための鍵となる。

この「Take / Not Take」パターンとは、一歩進むごとに、通常二つの選択肢のどちらかを選ぶというものだ。一つは「Take（取る）」、つまり現在の要素や項目を考慮に入れ、それに応じて問題を解決するための状態を更新する選択。もう一つは「Not Take（取らない）」、つまり現在の要素や項目をスキップして無視し、次の状態へと進む選択である。この二者択一の考え方が、多くの再帰的な解決策の基盤となり、メモ化やテーブル化といった手法を用いることで動的計画法へと自然に発展していく。

一般的な再帰のテンプレートを考えてみよう。ある状態が与えられたときに、まず問題の終点である「ベースケース」に到達したかどうかを確認する。到達していれば、定義された結果を返す。そうでない場合、二つの主要な選択肢を検討する。一つは現在の要素を「取る」選択だ。これによって状態が更新され、この新しい状態に対して再度同じ関数を呼び出す。もう一つは現在の要素を「取らない」選択だ。これもまた別の新しい状態へと繋がり、その状態に対して関数を呼び出す。最終的に、これら「取る」と「取らない」の両方の選択肢から得られた結果を、問題の目的に合わせて（例えば最大値、最小値、合計値など）組み合わせることで、現在の状態における最適解や目標とする結果を得るのだ。

具体的な例として、まず「コインチェンジ問題（最小枚数）」を見てみよう。これは、与えられた複数の種類のコインと目標金額に対して、その金額を作るのに必要な最小のコイン枚数を求める問題である。この問題に「Take / Not Take」パターンを適用すると、現在のコインを「取る」か「取らない」かで二つの選択肢が生まれる。現在のコインを「取らない」選択をした場合、そのコインは使わず、次に小さい（または別の種類の）コインを使って残りの金額を作ることを考える。一方、現在のコインを「取る」選択をした場合、そのコインを一度使い、必要な金額からそのコインの価値を引く。ここで重要なのは、多くのコインチェンジ問題では同じ種類のコインを何枚でも使えるため、「取る」選択をした後も、引き続きそのコインを使って残りの金額を作れる可能性がある点だ。これら二つの選択肢から得られる結果のうち、より少ないコイン枚数で目標金額を作れる方を選ぶことで、問題を解決していく。

次に「最長増加部分列（LIS）問題」を考えてみる。これは、与えられた数字の配列の中から、厳密に増加する部分列の中で最も長いものの長さを求める問題である。ここでも「Take / Not Take」の考え方が役立つ。現在の要素を部分列に「含めない（Not Take）」場合、その要素は無視し、次の要素へと進む。部分列の長さは変わらない。一方、現在の要素を部分列に「含める（Take）」場合、一つの条件がある。それは、その要素が部分列の直前の要素よりも大きい場合に限るというものだ。この条件を満たせば、部分列の長さは1増え、現在の要素を新たな「直前の要素」として、次の要素以降を検討する。この二つの選択肢から得られる部分列の長さのうち、より長い方を選ぶことで、最長増加部分列の長さを特定できる。

もう一つの例として、「単語分割（Word Break）問題」がある。これは、与えられた文字列が、辞書に含まれる単語をいくつか組み合わせて分割できるかどうかを判断する問題だ。この問題の場合、「Take / Not Take」のパターンは少し形を変えて現れる。現在の文字列のインデックスから始まる部分文字列に対して、辞書内の各単語を一つずつ「取る」ことを試みる。もしある単語で文字列が分割できたなら、残りの部分文字列に対して同じ問題を再帰的に解く。この場合、明示的に「取らない（Not Take）」という分岐は書かれないことが多いが、現在のインデックスから始まる部分文字列に対して、辞書内のどの単語も当てはまらない、あるいは当てはめても残りの文字列が分割できない場合、それは暗黙的に「Not Take」の経路が失敗したことを意味し、最終的に「分割できない」という結論につながる。つまり、成功する「Take」の経路が一つでも見つかれば全体として成功であり、どの「Take」も成功しない場合は、全体として失敗と判断されるのだ。

このように「Take / Not Take」パターンが多くの問題で有効なのは、問題をより小さな部分問題へと分解できるからだ。再帰によって、この選択を繰り返すことで最終的な解に到達する。バックトラッキングでは、この「取るか取らないか」という選択肢をすべて試すことで、可能なすべての解を探索する。そして動的計画法では、同じ部分問題が何度も計算されるのを避けるために、一度計算した結果を保存（メモ化）したり、下から順に解を構築（テーブル化）したりすることで、計算効率を大幅に向上させるのだ。

問題に直面した際に「Take / Not Take」パターンを適用できるかどうかを見極めるためには、自分自身にいくつかの問いを投げかけると良い。現在の要素や項目を「選ぶ」ことができるか？現在の要素や項目を「スキップする」ことができるか？それぞれを選択した後、状態はどのように変化するのか？そして、「取る」と「取らない」の両方の選択肢から得られた結果を、どのように組み合わせることで最終的な答えにたどり着くのか？これらの問いに明確に答えられる場合、このパターンが適用できる可能性が高い。

「Take / Not Take」は、再帰、バックトラッキング、動的計画法を用いる多くのアルゴリズム問題の根幹をなす考え方である。それは、カウント、最大化、最小化、あるいは特定のシーケンスの構築といった多岐にわたる課題に適用可能だ。ナップサック問題、コインチェンジ問題、単語分割問題、最長増加部分列問題、組み合わせ合計問題など、このパターンを練習することで、システムエンジニアとして必要なアルゴリズム的思考力を着実に高めることができるだろう。