【ITニュース解説】How to Decide the Size and Dimensions of Memoization or DP Arrays

動的計画法（DP）やメモ化は、再帰的な問題を効率的に解決するための非常に強力なプログラミング手法である。しかし、これらの手法を使う際に多くのプログラマが直面する共通の課題がある。それは、計算結果を一時的に保存しておくための「キャッシュ」や「DP配列」のサイズと次元をどのように決めるかという問題だ。この決定は極めて重要で、なぜなら全てのサブ問題の解が適切に保存され、結果が上書きされたり、余分なメモリを浪費したりするのを防ぐからである。

DP配列やメモ化配列は、それぞれが特定の「サブ問題」の解決策を格納するための場所である。この配列のサイズや形を決めるためには、まず「状態変数」という概念を理解する必要がある。状態変数とは、ある特定のサブ問題を他のサブ問題から一意に区別し、定義するためのパラメータのことだ。例えば、「コインの種類と残りの金額」が決まれば、特定のサブ問題が決まる、といった具合である。DP配列の次元は、これらの状態変数の数に直接対応する。一つの状態変数があるならば、一次元のDP配列（例：dp[サイズ]）が使われる。複数の状態変数があるならば、それに対応して多次元のDP配列（例：dp[サイズ1][サイズ2]）が必要になる。

DP配列のサイズを決定するためには、いくつかの段階を踏む必要がある。まず、再帰関数が受け取る引数の中で、結果に影響を与える全てのパラメータをリストアップする。これらが状態変数となる。次に、リストアップした各状態変数が取りうる値の有効な「範囲」を決定する。例えば、配列のインデックスを表す変数であれば、その最大インデックスに1を加えた値が配列のサイズとなる（maxIndex + 1）。金額や合計値を表す変数であれば、取りうる最大値に1を加えた値がサイズとなる（maxValue + 1）。これは、配列のインデックスが0から始まるため、最大値までを格納するためには「最大値+1」の大きさが必要になるという考え方だ。

さらに、DP配列に何を格納するかによって、配列の型を選ぶ必要がある。例えば、ある条件が真か偽かを示す場合はBoolean型の配列を、数値の個数、最小値、最大値などを格納する場合はInteger型やint型の配列を使用する。また、状態変数が負の値を取る可能性がある場合には特別な処理が必要となる。配列のインデックスは0以上の整数でなければならないため、負の値をそのままインデックスとして使うことはできない。この問題を解決するには、「オフセット」という手法を使う。これは、負の値を含む状態変数に一定の数値を加えることで、常に0以上の正のインデックスに変換する方法である。例えば、-1から始まるインデックスがある場合、全ての値に1を加えることで0から始まるインデックスに変換し、配列に格納する。状態変数が複数ある場合は、それぞれの状態変数に対応する次元を持つ多次元配列を割り当てることになる。

いくつかの具体例を見てみよう。「コインチェンジ問題」では、「利用できるコインの種類」と「残りの金額」という二つの要素がサブ問題を定義する。つまり、coinIndexとremainingAmountという二つの状態変数がある。coinIndexは0からn-1（nはコインの種類の数）までの範囲を取り、remainingAmountは0から目標金額amountまでの範囲を取る。したがって、DP配列はInteger[n][amount + 1]のように二次元で宣言される。

次に「最長増加部分列（LIS）問題」では、「現在のインデックスcurrentIndex」と「直前の要素のインデックスprevIndex」が状態変数となる。currentIndexは0からn-1（nは数列の長さ）の範囲を取り、prevIndexは-1（まだ前の要素がない場合）からn-1までの範囲を取る。ここでprevIndexが-1という負の値を含むため、オフセットが必要となる。prevIndexに1を加えることで、prevIndex + 1は0からnまでの範囲となり、これを配列のインデックスとして使用できる。結果として、DP配列はInteger[n][n + 1]のように宣言される。

「単語分割問題」では、「現在の文字列の開始インデックスcurrentIndex」だけが状態変数となる。currentIndexは0から文字列の長さs.length()までの範囲を取る。そのため、DP配列はBoolean[s.length() + 1]のように一次元で宣言される。ここではs.length()までを含むため、サイズはs.length() + 1となる。

DP配列を設計する上で重要な原則は、まず「全ての状態変数を漏れなく含める」ことだ。一つでも欠けていると、サブ問題の定義が曖昧になり、誤った結果を導き出す可能性がある。次に、「次元のサイズは最大値に1を加える」という原則を厳守すること。これにより、取りうる全ての値が配列に適切に収まることを保証できる。そして、「負のインデックスは必ずオフセットで正のインデックスに変換する」こと。配列は負のインデックスを扱えないため、この処理は必須である。最後に、格納する値に応じてBoolean、Integer、intなど、「適切な配列の型を選択する」ことも重要だ。これらの原則を無視すると、例えば状態変数が二つあるのに一次元配列を使ってしまい結果が間違ったり、配列サイズが不適切でインデックス範囲外エラーが発生したり、負のインデックスの扱いで問題が起きたりするなどの「落とし穴」にはまってしまう可能性がある。

動的計画法やメモ化における配列の設計は、成功するソリューションを構築するための基盤となる。サブ問題を一意に定義する全てのパラメータを特定し、それらが取りうる値の範囲と、必要であれば負のインデックスを正に変換するためのオフセットを正確に決定することが重要だ。そして、これらの情報に基づいて適切な次元と型の配列を割り当てる。これらの手順を注意深く実行することで、あなたの再帰的またはDPソリューションは正しく、効率的になり、重複する計算を避け、最適なパフォーマンスを発揮できるようになるだろう。