Code Kata | day13 min_path_sum


Q.正数mxnグリッドをパラメータとする.上から左へ、下から右へ行く道のすべての要素を加える場合は、最小の和を見つけて返します.

☑️ code


リストを下に重ねます.mは横長,nは縦長である.下図のように、右または下の値を加算した累積値に移動するだけです.(4=1+3、5=4+1で、4は同じ4です.)
def min_path_sum(grid):
  
  m = len(grid[0])
  n = len(grid)
  for i in range(1, m):
    grid[0][i] += grid[0][i-1]
  for i in range(1, n):
    grid[i][0] += grid[i-1][0]
  for i in range(1, n):
    for j in range(1, m):
      grid[i][j] += min(grid[i-1][j], grid[i][j-1])
  
  return grid[-1][-1]
  
Review
このアルゴリズム問題は,新しい関数や方法を用いるよりも,答えを見つける方法を考え出すことが難しい.できるだけ多くの接触と新しい方法を考える方法自体を訓練することが重要です.