概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
初めにDP（動的計画法）に慣れるためにDPを使用した解き方を行いたいと思います。
DPを使用すると計算量・空間量はO(mn)となるため、その後別の解き方で高速化を図りたいと思います。
問題
m×nのグリッド上にロボットがいる。ロボットは最初左上に位置している（すなわち、grid[0][0]）。ロボットは右下（つまりgrid[m - 1][n - 1]）に移動しようとする。ロボットはどの時点でも、下か右のどちらかにしか移動できない。
2つの整数 m と n が与えられたとき，ロボットが右下隅に到達するために取り得るユニークな経路の数を返せ．
テストケースは，答えが 2 * 109以下になるように生成される．
制約
1 <= m, n <= 100
解説
DPテーブルの作成
まず初めにDPテーブルを作成します。
作成するテーブルは開始位置からゴールまで何パターンの移動方法があるかを考えます。(2,2)に移動する場合は開始位置の下から移動した場合と右から移動した場合の2パターン、(2,3)は開始位置の下から進むパターンと、右に１マス進んで下に移動しもう一度右に進むパターンと、初めに右に3マス進むパターンの3パターンになります。
このように考えていくとこのようなテーブルになります。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
作成途中でパターンに気付いた方もいらっしゃると思いますが、ゴールに行くためには左からか上からしかゴールできません。となると、左から来るパターンの数と、上から来るパターンを足せばゴールにたどり着くパターンが見えてくるわけです。
つまり(m,n)にたどり着くには(m-1,n)にたどり着くパターンの数と、(m,n-1)にたどり着くパターンの数を足せば求められます。
コードでの表し方
DPテーブルが完成しパターンが見えてきたので、コードに表していきましょう。
まずはテーブルを作成し、最初の行と最初の列に1を格納する。
// 空のDPテーブル作成
var dp = new int[m, n];
// 1パターンとなるデータを1で埋める
for (int i = 0; i < m; i++)
{
dp[i, 0] = 1;
}
for (int i = 0; i < n; i++)
{
dp[0, i] = 1;
}// 行ごとのループ
for (int i = 1; i < m; i++)
{
// 列ごとのループ
for (int j = 1; j < n; j++)
{
// 対象のマスに左と上のマスを合計値を入れる
dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
}
}
// ゴールのマスの値を返す
return dp[m - 1, n - 1];テーブルと初期データが用意できたら行・列でループを二重にネストさせ、対象のマスに左と上のマスの値を足して格納する。最後にゴールのマスのデータを返して終了です。
これで計算量・空間量がO(mn)となる解答が出ました。
ですがさらに改善できる余地があるので次の項目で改善していきます。
１度目の改善
先ほど記載したコードのこのコードに注目しましょう。
// 行ごとのループ
for (int i = 1; i < m; i++)
{
// 列ごとのループ
for (int j = 1; j < n; j++)
{
// 対象のマスに左と上のマスを合計値を入れる
dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
}
}ここで使用しているのは対象のマスの直前のマスと上にあるマスしか使用していません。テーブルを作成していますが、すべてのデータを毎回使用しているわけではないので、余分な空間コストがかかってしまっています。
使用しているデータはfor文で行ごとに使用していることを踏まえると、現在探索している行と直前の行の2行になることが分かります。
早速ソースコードに表してみましょう
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| previous | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| current | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| previous | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| current | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
public int UniquePathsWithDPFix1(int m, int n)
{
// 直前の行と現在の行
var previous = new int[n];
var current = new int[n];
// 最初の行に1を入れる
for (int i = 0; i < n; i++)
{
previous[i] = 1;
}
// 一番最初の列は1なのでcurrent[0]に1を入れる
current[0] = 1;
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
// 直前の行の同じ列と現在の行の直前の列を足す
current[j] = previous[j] + current[j- 1];
}
// 次の行に移動する前にデータをコピーする
current.CopyTo(previous, 0);
}
return current[n - 1];
}これで、空間コストがO(n)となりました。
ですがさらにもう一つ改善できる箇所がありますのでさらに改善します。
１度目の改善
もう一つ改善できる箇所というのは直前の行を同じ配列で表すことです。
先ほどは1行目・1列目のデータを最初に配列に入れループは2行目・2列目から探索していきましたね。
まずは1週目と2週目を確認しましょう。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| previous | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| current | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| previous | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| current | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
そうです。最後にコピーしているので2回目以降の更新前のデータは同じになります。
ですので、現在探索しているマスの直前の行の同じ列のデータを使用する代わりに、現在探索しているマスを使用すれば直前の行というものがいらなくなります。１行目に関しては1で初期化すれば解決します。
それでは最終的なソースコードです。
public int UniquePathsWithDPFix2(int m, int n)
{
// 最初の行を配列に入れる
var nums = new int[n];
for (int i = 0; i < n; i++)
{
nums[i] = 1;
}
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
// 直前のデータを対象のマスに加算する
nums[j] += nums[j - 1];
}
}
return nums[n - 1];
}ソースコード
public class Solution {
public int UniquePathsWithDPFix2(int m, int n)
{
// 最初の行を配列に入れる
var nums = new int[n];
for (int i = 0; i < n; i++)
{
nums[i] = 1;
}
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
// 直前のデータを対象のマスに加算する
nums[j] += nums[j - 1];
}
}
return nums[n - 1];
}
}いかがでしょうか。様々なDP問題がありますが、DPで見つけた解答で満足しにてしまいますよね。ですがこのように改善できる場合があるので無駄がないか再確認することをお勧めいたします。