Pythonで解くユニークパス問題：動的計画法で経路の総数を求める方法

ユニークパス（Unique Paths）問題とは

n行m列のグリッドの左上のマスにロボットが配置されているとします。ロボットは任意の時点で「下」または「右」のどちらかにのみ移動でき、グリッドの右下のマス（下の図では「END」と表示）を目指します。このとき、始点から終点まで到達できる経路が何通り存在するかを求めるのが、この「ユニークパス」問題です。

例として、m = 3、n = 2 の場合、グリッドは次のようになります。

この場合の出力は 3 です。つまり、開始位置から終了位置まで到達する方法は全部で3通りあります。それぞれの経路は以下の通りです。

1. 右 → 右 → 下
2. 右 → 下 → 右
3. 下 → 右 → 右

動的計画法による解法の手順

この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解くことができます。基本的な考え方は、「あるマスに到達する経路の数は、その下のマスと右のマスに到達する経路の数の合計に等しい」というものです。具体的な手順は以下の通りです。

• row := n、col := m とし、n × m のサイズのDPテーブルを作成して、すべての要素を -1 で初期化します。
• DP[row - 2, col - 1] := 1 を設定します。
• i を 0 から col までループさせ、DP[n - 1, i] := 1 を設定します（最下行の各マスには経路が1通りしかありません）。
• i を 0 から row までループさせ、DP[i, col - 1] := 1 を設定します（最右列も同様に1通りです）。
• i を row - 2 から -1 まで、j を col - 2 から -1 まで逆順にループさせ、DP[i, j] := DP[i + 1, j] + DP[i, j + 1] を計算します。
• 最後に DP[0, 0] を返します。これが求める経路の総数となります。

Pythonでの実装例

それでは、実際の実装を見ていきましょう。理解を深めるために、以下のコードを参考にしてください。

class Solution(object):
    def uniquePaths(self, m, n):
        row = n
        column = m
        dp = [[-1 for i in range(m)] for j in range(n)]
        dp[row-2][column-1] = 1
        for i in range(column):
            dp[n-1][i] = 1
        for i in range(row):
            dp[i][column-1]=1
        for i in range(row-2,-1,-1):
            for j in range(column-2,-1,-1):
                dp[i][j] = dp[i+1][j] + dp[i][j+1]
        return dp[0][0]
ob1 = Solution()
print(ob1.uniquePaths(10,3))

入力

10
3

出力

55

この例では、10列×3行のグリッドにおける経路の総数として 55 が出力されます。動的計画法を用いることで、すべての経路を列挙することなく、計算量 O(n × m) で効率的に答えを求めることができます。