概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
m×nの整数配列のgridが与えられる。
初期状態では左上隅（grid[0][0]）にロボットが配置されている。
ロボットは右下隅（grid[m-1][n-1]）に移動しようとする。
ロボットはどの時点でも、下か右のどちらかにしか移動できない。
grid内では障害物は1、通れる空間は0と表示される。
ロボットが通る道には、障害物であるマスを含むことができない。
ロボットが右下隅に到達するために取り得るユニークな経路の数を返す。
テストケースは、答えが2 * 109以下になるように生成される。
制約
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]is0or1.
解説
前提問題
この問題は62. Unique Pathsの派生問題です。まだ解いていない方はこちらを参考に解くことをお勧めいたします。
C#で解くLeetCode「62. Unique Paths」
DPテーブルの作成
まず初めにDPテーブルを作成します。
作成するテーブルは開始位置からゴールまで何パターンの移動方法があるかを考えます。障害物はXで表しています。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | X | 0 |
| 2 | X | X | 1 | 2 | 3 | 3 | X |
| 3 | 0 | 0 | 1 | X | 3 | 6 | 6 |
62. Unique Pathsと同じように今回もロボットは右と下にしか進めないため、左から来るパターンの数と、上から来るパターンを足せばゴールにたどり着くパターンが見えてくるわけです。
違う点はXが0として足されているという点です。
コードでの表し方
DPテーブルが完成しパターンが見えてきたので、コードに表していきましょう。
まずは行を表す配列を作成し、最初のマスに1を格納します。
var width = obstacleGrid[0].Length;
var patternCounts = new int[width];
patternCounts[0] = 1;初期データが用意できたら行・列でループを二重にネストさせ1行ずつ、そして1マスずつ探索処理を進めていきます。
対象のマスに障害物があるかを確認して障害物にはたどり着けないので0を格納します。
障害物がなければ前回と同じようにすでに入っている値を対象の上のマスとして、直前の値を左のマスとしてパターン数を合計します。
この際1列だった場合は左を足せないので除外してください。
配列の最後の値が目的地へたどり着くルートのパターン数となるので返して終了です。
foreach (var row in obstacleGrid)
{
for (int i = 0; i < width; i++)
{
// 対象のマスが障害物だったら0パターンとする
if (row[i] == 1)
{
patternCounts[i] = 0;
}
// 1列だった場合は左を足せないので除外する
else if (i > 0)
{
patternCounts[i] += patternCounts[i - 1];
}
}
}
return patternCounts[width - 1];ソースコード
public class Solution {
public int UniquePathsWithObstacles(int[][] obstacleGrid)
{
var width = obstacleGrid[0].Length;
var patternCounts = new int[width];
patternCounts[0] = 1;
foreach (var row in obstacleGrid)
{
for (int i = 0; i < width; i++)
{
// 対象のマスが障害物だったら0パターンとする
if (row[i] == 1)
{
patternCounts[i] = 0;
}
// 1列だった場合は左を足せないので除外する
else if (i > 0)
{
patternCounts[i] += patternCounts[i - 1];
}
}
}
return patternCounts[width - 1];
}
}いかがでしょうか。様々なDP問題がありますが、DPで見つけた解答で満足しにてしまいますよね。ですがこのように改善できる場合があるので無駄がないか再確認することをお勧めいたします。