Leetcodeで面白い問題があったので解決方法をここでメモします。
問題内容（英語）
https://leetcode.com/problems/minimum-path-sum/description/
与えられたグリッドの左上([0,0])から右下([2,2])に移動し、その移動経路（パス）に沿ったすべての要素の和を最小にします。
注意点：移動方向は右か下かのどちらだけとなります。
例：
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となります。
解決方法
方法はたくさんありますが、ここでは私が使った方法を説明します。
考え方が簡単ですが、次のステップでどの要素に移動するかが分かれば、
計算がやりやすいです。そのために、各要素の重み(weights)が必要となります。
ここでは逆方向ですべての要素の重みを計算します。
各要素の重みは一個右と一個下の要素が持っている重みが小さいほうの値とこの要素自身の値の和となります。
一番右下の要素の重みは自分自身の値とします。
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]
最短経路で[0,0]から[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