음이 아닌 정수로 채워진 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):""" :type grid:List[List[int]] :rtype:int """ row =len(grid)-1 column =len( grid[0])-1 i=row-1 j=column-1 동안 j>=0:grid[row][j]+=grid[row][j+1] j-=1 동안 i>=0 :grid[i][column]+=grid[i+1][column] i-=1 j=column-1 i =row-1 동안 i>=0:j>=0:grid[i][ j] +=min(그리드[i][j+1],그리드[i+1][j]) j-=1 j=열-1 i-=1 return(그리드[0][0])입력
[[1,3,1],[1,5,1],[4,2,1]]출력
7