コーディングの面接では、ダイナミックプランニングの問題は非常に威圧的であることは間違いないでしょう。ダイナミックプランニングの手法で問題を解決する必要があるとわかっていても、限られた時間の中で実行可能な解決策を導き出すことは困難です。

動的計画問題に習熟するには、できるだけ多くの問題を研究することです。それぞれの問題に対する解決策を必ずしも覚える必要はありませんが、実装の進め方のイメージは持っておくとよいでしょう。

ダイナミックプログラミングは何ですか？

簡単に言えば、動的計画法は再帰的アルゴリズムの最適化手法であり、その多くは計算問題や数学的問題の解決に用いられるものである。

また、最適化問題をより単純なサブ問題に分解して解決するアルゴリズム手法と呼ぶこともできる。動的計画法の重要な原則は、問題の最適解が部分問題の解に依存することである。

同じ入力に対して再帰的な解が繰り返し呼び出されるのを見るたびに、動的計画法を使って最適化することができる。サブ問題の結果を単純に保存しておくことで、後で必要なときに再計算する必要がないようにするためだ。

動的計画法の解は多項式であり、再帰やバックトラックなどの他の手法よりも高速な実行時間を保証する。多くの場合、動的計画法はビッグ・オーとも呼ばれる時間複雑性を指数関数的なものから多項式に減らすことができる。

さて、ダイナミック・プランニングとは何か、よく理解できたところで、次によくある問題とその解決策を検討しましょう。

動的計画問題

1 バックパックの問題

問題提起

重さと値を持つ品目の集合が与えられたとき、重さの合計が与えられた制限を超えず、値の合計ができるだけ大きくなるように、集合に含まれるべき各品目の数を決定しなさい。

値 [0..n-1] と重み [0..n-1] の2つの整数配列が用意されており、それぞれn個のアイテムに関連する値と重みが表現されています。また、パックの容量を示す整数Wが付与される。

ここでは、0/1バックパックの問題に取り組んでいます。つまり、アイテムを追加したり除外したりするオプションがあるということです。

アルゴリズム

• n+1行、w+1列の2次元配列を作成する。行番号nは1～iのアイテム群、列番号wは荷物の最大積載量を示しています。
• i][j]の値は、iまでの最大重量jを運ぶことができるバッグの中のアイテムの合計値を示す。
• 配列の各座標[i][j]において、i項を含まない最大値と、i項を含む最大値のどちらか大きい方を選ぶ。
• 1個目を含むことで得られる最大値は、1個目そのものとパックの残容量で得られる最大値の和となる。
• このステップをw行の最大値が見つかるまで行う。

コード

def FindMax(W, n, values, weights): MaxVals = [[0 for x in range(W + 1)] for x in range(n + 1)] for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: MaxVals[i][w] = 0 elif weights[i-1] <= w: MaxVals[i][w] = max(values[i-1] + MaxVals[i-1][w-weights[i-1]], MaxVals[i-1][w]) else: MaxVals[i][w] = MaxVals[i-1][w] return MaxVals[n][W]

2 コイン交換の問題

問題提起

ある数量が与えられたとき、この数量を**するために必要な最小のコインの枚数を求めよ。

アルゴリズム

• サイズ n+1 の配列を初期化する。配列の各インデックスiの値をamountに初期化する。これは、その金額を構成するのに必要なコインの最大枚数を示す（額面1枚のコインを使用）。
• 0は名前がないので、配列[0]=0を初期化する基本ケース。
• 他の各インデックスiについて、その中の値（初期値はn+1）と、値の配列[i-k]+1（kはiより小さい）を比較する。これは実質的に、i-1までの配列全体をチェックして、使用できる最小のコインの数を見つけることである。
• 任意の配列[i-k]+1の値が既存の配列[i]の値より小さい場合、配列[i]の値を配列[i-k]+1の値で置き換えます。

コード

def coin_change(d, amount, k): numbers = [0]*(amount+1) for j in range(1, amount+1): minimum = amount for i in range(1, k+1): if(j >= d[i]): minimum = min(minimum, 1 + numbers[j-d[i]]) numbers[j] = minimum return numbers[amount]

III.フィボナッチ

問題提起

フィボナッチ級数とは、次の整数が最初の2つの整数の和になるような整数の並びのことである。

F(0) = 0、F(n) = F(n-1) + F(n-2) (F(n)は第n項)の漸化式で定義される。この問題では、与えられたn番目の項までのフィボナッチ級数のすべての数を生成する必要があります。

アルゴリズム

• まず、与えられた再帰的関係を再帰的手法で実装する。
• この問題を再帰的に解くには、F（n）をF（n-1）＋F（n-2）に分解し、F（n-1）とF（n＋2）を引数として関数を呼び出す必要があります。これを、n=0またはn=1の基本ケースに達するまで行う。
• 今は、メモリという技術を使います。すべての関数呼び出しの結果を配列に格納する。これにより、F(n)はすべてのnについて一度だけ計算されることになる。
• その後の計算では、その値を一定時間ごとに配列から取得すればよい。

コード

def fibonacci(n): fibNums = [0, 1] for i in range(2, n+1): fibNums.append(fibNums[i-1] + fibNums[i-2]) return fibNums[n]

4 後継者

問題提起

与えられた配列の中で、最も長く伸びる部分配列の長さを求めよ。最長増加部分配列とは、配列中の数値が増加する部分配列のことである。部分配列に含まれる数値は一意であり、昇順に並べられなければならない。

また、順番は連続である必要はない。

アルゴリズム

• 再帰的手法から始めて，インデックス0からインデックスiまでの可能性のある部分配列の最長インクリメンタル部分配列の値を計算する（iは配列のサイズ以下である）．
• このメソッドを動的メソッドに変換するには、各サブシーケンスの値を格納する配列を作成し、この配列の値をすべて0に初期化します。
• この配列の各インデックスiは，サイズiの部分配列の最長の部分配列の長さに対応する．
• さて，findLIS (arr, n)を再帰的に呼び出すたびに，配列のn番目のインデックスをチェックします．0の場合、手順1の方法で計算し、n番目のインデックスに格納します。
• 最後に，配列から最大値が返される．これは，与えられたサイズ n の最も長い部分配列の長さである．

コード

def findLIS(myArray): n = len(myArray) lis = [0]*n for i in range (1 , n): for j in range(0 , i): if myArray[i] > myArray[j] and lis[i]< lis[j] + 1 : lis[i] = lis[j]+1 maxVal= 0 for i in range(n): maxVal = max(maxVal , lis[i]) return maxVal

動的計画法の問題解決

さて、動的計画法の代表的な問題をいくつか学んだところで、いよいよ自分でこれらの解法を実装してみることにしましょう。もし行き詰まったら、いつでも戻ってきて、上記の各問題のアルゴリズムのセクションを参照することができます。

再帰や動的プログラミングのようなテクニックが最近いかに普及しているかを考慮し、これらのコンセプトを学び、コーディングスキルを磨くことができる人気のプラットフォームをいくつか紹介します。日常的に遭遇することはないかもしれませんが、技術系の面接では必ずと言っていいほど、これらの質問に遭遇することになります。

次の面接に行くときは、よくある質問のコツをつかんでおくと安心です。