動的計画法（ルートの数）

問題

縦 $ H $ 行、横 $ W $ 列のマス目があります。

上から $ i $ 行目、左から $ j $ 列目のマス $ (i,j) $ の色は $ c_{i,j} $ であり、$ c_{i,j} $ が . ならば白、 # ならば黒で塗られおり、黒マスは通ることができません。

マス $ (1,1) $ から出発し、右方向または下方向の移動をくりかえしてマス $ (H,W) $ まで行く方法は何通りありますか。

[制約]
🔹$ 2 \leqq H \leqq 30 $
🔹$ 2 \leqq W \leqq 30 $
🔹スタート地点 $ (1,1) $ とゴール地点 $ (H,W) $ は白マス

解き方・ソースコード

まず動的計画法で管理する配列を以下のように定義します。

🔹$ dp[i][j] $ ：マス $ (1,1) $ から $ (i,j) $ まで移動する方法の数

マス $ (i,j) $ に移動するには次の２つのパターンがあります。

🔹マス $ (i-1,j) $ ⇒ マス $ (i,j) $ に直接移動
🔹マス $ (i,j-1) $ ⇒ マス $ (i,j) $ に直接移動

黒マスがない状態で考えると次の式が成り立ちます。

🔹$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $

上記の式に「１列目１行目は必ず１パターンしかありえない」ということと「移動直前のマス目が黒マスの場合カウントしない」ことを踏まえて実装すると下記のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#--------- 入力例 ----------
H = 4   # 縦の行数
W = 8   # 横の列数
c = [
    ['.', '.', '.', '.', '#', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '#', '.'],
    ['.', '.', '#', '.', '.', '.', '#', '.'],
    ['#', '.', '.', '.', '.', '.', '.', '.'],
]
#---------------------------
# 確認のためにマス目の状態を出力
print('【マス目の状態】')
for i in range(H):
    for j in range(W):
      print(c[i][j], end='')
    print()
print()

# 動的計画法
dp = [ [ 0 ] * (W + 1) for i in range(H + 1) ]
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = 0
            if i >= 1 and c[i - 1][j]=='.':
                dp[i][j] += dp[i - 1][j]
            if j >= 1 and c[i][j - 1] == '.':
                dp[i][j] += dp[i][j - 1]

print('【移動する方法の数（マス目ごと）】')
for i in range(H):
    for j in range(W):
      print(f'{dp[i][j]:02d}', end=' ')
    print()
print()

# 出力
print('解：', dp[H - 1][W - 1])

[実行結果]

【マス目の状態】
....#...
......#.
..#...#.
#.......

【移動する方法の数（マス目ごと）】
01 01 01 01 01 00 00 00 
01 02 03 04 04 04 04 00 
01 03 06 04 08 12 12 00 
01 03 03 07 15 27 27 27 

解： 27

今回の入力例に関しては、27通りのルートがあることを導き出すことができました。