[LeetCode] 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

반응형

---

좌상단에서 우하단까지 갈 때 각 타일에 적힌 값을 더하고 최종 목적지에서 그 값이 최소값이 나오도록 하는 문제이다.

2중 for문을 돌며 과거 수학 문제 길찾기처럼 이전의 길(x축으로 좌측 혹은 y축으로 위)에서 가장 작은 값을 가져와 현재 값과 더하여 해당 위치까지의 최소값을 구하며 진행한다. 끝까지 반복 후 최종 목적지의 값이 최소값이 된다.

 

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        for i in range(0, m):
            for j in range(0, n):
                if i-1 < 0 and j-1 < 0:
                    continue
                elif i-1 < 0 and j-1 >= 0:
                    grid[i][j] += grid[i][j-1]
                elif j-1 < 0 and i-1 >= 0:
                    grid[i][j] += grid[i-1][j]
                else:
                    grid[i][j] += grid[i-1][j] if grid[i-1][j] < grid[i][j-1] else grid[i][j-1]
        answer = grid[m-1][n-1]
        return answer

 

문제 출처 : https://leetcode.com/problems/minimum-path-sum/

Minimum Path Sum - LeetCode

Github : https://github.com/kkkkang1009/leetcode/blob/master/leetcode_64.py

GitHub - kkkkang1009/leetcode: leetcode