Python의 최소 경로 합계

<시간/>

음이 아닌 정수로 채워진 m x n 행렬이 있다고 가정하고 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 경로를 따라 모든 숫자의 합을 최소화하는 경로를 찾습니다. 움직임은 어느 시점에서든 아래 또는 오른쪽에만 있을 수 있습니다. 예를 들어 행렬이 아래와 같다면

1	3	1
1	5	1
4	2	1

출력은 7이고 경로는 1,3,1,1,1이 됩니다. 이렇게 하면 합계가 최소화됩니다.

단계를 살펴보겠습니다 -

a :=행 수, b :=열 수
i :=a – 1, j :=b – 1
동안 j>=0
- 행렬[a, j] :=행렬[a, j] + 행렬[a, j + 1]
- j를 1 감소
내가>=0
- 행렬[i, b] :=행렬[i, b] + 행렬[i + 1, b]
- i를 1 감소
j :=b – 1 및 i :=행 – 1
내가>=0
- 동안 j>=0
  - 행렬[i, j] :=행렬[i, j] + 행렬[i, j + 1] 및 행렬[i + 1, j]의 최소값
  - j를 1 감소
- j :=b – 1
- 나는 :=나는 – 1
반환 행렬[0, 0]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution(object):
   def minPathSum(self, grid):
      row = len(grid)-1
      column = len(grid[0])-1
      i=row-1
      j=column-1
      while j>=0:
         grid[row][j]+=grid[row][j+1]
         j-=1
      while i>=0:
         grid[i][column]+=grid[i+1][column]
         i-=1
      j=column-1
     i = row-1
      while i>=0:
         while j>=0:
            grid[i][j] += min(grid[i][j+1],grid[i+1][j])
            j-=1
         j=column-1
         i-=1
      return(grid[0][0])
ob1 = Solution()
print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))

입력

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