パスの最小値と

質問する
パラメータとして正のmxnグリッドを使用します.
上から左へ、下から右へ行く道のすべての要素を加える場合は、最小の和を見つけて返します.
1つのポイントでのみ右または下に移動できます.
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
説明:1→3→1→1→1→1→1の和最小
私の答え
BREADTH First Searchを学んだ人なら、この問題は簡単に解決できます.

queueを使用して、最初の位置で表示できるすべての座標と、2番目の位置で表示できるすべての座標...nはn番目の位置で、すべての可能な座標が腕立て伏せである.

を通過したすべての座標で和を求める.

種の着地からルートを経て、比較して和を求め、最小値を選択します.

主な論理は以下の通りである.

題では、右と下にしか歩けないと言っています.右に行くためには、(x,y)座標にyの値1を加えることができます.下に行くためには、xの値に1を加えることができます.
右下隅の使用を容易にするために、direct変数で右上隅座標と下角座標を事前に定義します.

初期開始点の座標(0,0)と(0,0)の座標値をリストに入れて、キュー内の要素として使用します.
始点値と始点値を含むリストを最初の値として任意の指定qに入れる.

の最初のqの要素をtemp変数に文として、右、下座標をdx、dy変数に、dx、dy変数に入力配列サイズ以上のものがあれば、配列の範囲外とみなす.

for文を回し、移動可能座標の値dxとdyをリストの1番目、2番目の要素とし、既存座標の値とdx、dy座標の値を加算してリストの3番目の要素とする.
リストにqの要素として追加します.

qが

ビットプロシージャを求める前に、最初から最後まで移動するすべての座標を繰り返し計算するので、最終宛先で値を比較し、最小値minで返す.

def min_path_sum(grid):
  m = len(grid)
  n = len(grid[0])

  node = [0, 0, grid[0][0]]
  q = [node]
  direct = [
    [0, 1],
    [1, 0]
  ]

  min = 999999

  while(True):
    if not q: break

    temp = q.pop(0)

    for i in range(2):
      dx = temp[0] + direct[i][0]
      dy = temp[1] + direct[i][1]

      if dx >= m or dy >= n: continue
      if (dx == m - 1 and dy == n - 1) and min > temp[2] + grid[dx][dy]:
        min = temp[2] + grid[dx][dy]

      sum = temp[2] + grid[dx][dy]
      q.append([dx, dy, sum])

  return min