0

More than 3 years have passed since last update.

posted at

updated at

# 最短経路（minimum path sum）検索方法メモ

Leetcodeで面白い問題があったので解決方法をここでメモします。

``````input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7

[0,0] → [0,1] → [0,2] → [1,2] → [2,2]
1   +   3   +   1   +   1   +   1
なので、合計は7となります。
``````

#### 解決方法

ここでは逆方向ですべての要素の重みを計算します。

3x3のグリッドを例として

``````[2,2] → [2,1] → [2,0] → [1,2] → [1,1] → [1,0] → [0,2] → [0,1] → [0,0]
``````

の順番で重みを計算していく感じです。

``````[1,3,1]    [999,999,999]
[1,5,1]    [999,999,999]
[4,2,1]    [999,999,1]
``````

g：グリッド
w_g：グリッドの重み

``````[1,3,1]    [999,999,999]
[1,5,1]    [999,999,999]
[4,2,1]    [999,3,1]
＃w_g[2,1] = g[2,1] + w_g[2,2]
2   +    1    =3

↓

[1,3,1]    [999,999,999]
[1,5,1]    [999,999,999]
[4,2,1]    [7,3,1]
＃w_g[2,0] = g[2,0] + w_g[2,1]

↓

[1,3,1]    [999,999,999]
[1,5,1]    [999,999,2]
[4,2,1]    [7,3,1]
＃w_g[1,2] = g[1,2] + w_g[2,2]
1    +   1     =2

↓

[1,3,1]    [999,999,999]
[1,5,1]    [999,7,2]
[4,2,1]    [7,3,1]
＃w_g[1,2](2) < w_g[2,1](3)
＃w_g[1,1] = g[1,1] + w_g[1,2]
5   +   2     =7

↓

[1,3,1]    [999,999,999]
[1,5,1]    [8,7,2]
[4,2,1]    [7,3,1]
＃w_g[2,0] == w_g[1,1] == 7 この場合どちらに移動しても同じ結果なので、どちらを選択しても構いません。
＃w_g[1,0] = g[1,0] + 7
1   + 7 = 8

↓

[1,3,1]    [999,999,3]
[1,5,1]    [8,7,2]
[4,2,1]    [7,3,1]
＃w_g[0,2] = g[0,2] + w_g[1,2]
1   +    2    =3

↓

[1,3,1]    [999,6,3]
[1,5,1]    [8,7,2]
[4,2,1]    [7,3,1]
＃w_g[0,2](3) < w_g[1,1](7)
＃w_g[0,1] = g[0,1] + w_g[0,2]
3   +    3    =6

↓

[1,3,1]    [7,6,3]
[1,5,1]    [8,7,2]
[4,2,1]    [7,3,1]
＃w_g[0,1](6) < w_g[1,0](8)
＃w_g[0,0] = g[0,0] + w_g[0,1]
1   +    6    =7
``````

ここでは

``````[7,6,3]
[8,7,2]
[7,3,1]

start at [0,0]
[0,0] → [0,1] → [0,2] → [1,2] → [2,2]
``````

#### ソースコード

ここのソースコードはLeetcodeのweb上で検証のためのものとなり、PC環境で直接実行できないので、ご注意ください。
また、コードの判断ロジックを複雑にしないために、重みのグリッドサイズを縦と横に+1のサイズで生成します。
grid size : 3x3
weight size: 4x4

``````class Solution:
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""

# 重み計算
w_grid = [[ 999 for i in range(len(grid[0])+1)] for i in range(len(grid)+1)]
for i in range(len(grid)-1, -1, -1):
for j in range(len(grid[0])-1, -1, -1):
if j < len(grid[0]) - 1 and i < len(grid) - 1:
if w_grid[i+1][j] <= w_grid[i][j+1]:
w_grid[i][j] = w_grid[i+1][j] + grid[i][j]
else:
w_grid[i][j] = w_grid[i][j+1] + grid[i][j]
elif j == len(grid[0]) - 1 and i == len(grid) - 1:
w_grid[i][j] = grid[i][j]
elif j == len(grid[0]) - 1:
w_grid[i][j] = w_grid[i+1][j] + grid[i][j]
elif i == len(grid) - 1:
w_grid[i][j] = w_grid[i][j+1] + grid[i][j]
else:
continue

# 最短経路の各要素の和の計算
p_x, p_y = 0, 0
rst = grid[0][0]
for _ in range(len(grid) + len(grid[0]) - 2):
if w_grid[p_x + 1][p_y] <= w_grid[p_x][p_y + 1]:
rst += grid[p_x + 1][p_y]
p_x += 1
else:
rst += grid[p_x][p_y + 1]
p_y += 1

return rst
``````

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
What you can do with signing up
0