파비의 매일매일 공부기록

2023.03.27 Today's Challenge 본문

Problem Solving/LeetCode

2023.03.27 Today's Challenge

fabichoi 2023. 3. 27. 23:45

https://leetcode.com/problems/minimum-path-sum/

 

Minimum Path Sum - LeetCode

Can you solve this real interview question? 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 rig

leetcode.com

오랫만에 dp로 푸는 문제!

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        
        for i in range(1, n):
            grid[0][i] += grid[0][i-1]
        
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        
        return grid[-1][-1]
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.03.29 Today's Challenge  (0) 2023.03.29
2023.03.28 Today's Challenge  (0) 2023.03.28
2023.03.26 Today's Challenge  (0) 2023.03.26
2023.03.25 Today's Challenge  (0) 2023.03.25
2023.03.24 Today's Challenge  (0) 2023.03.24
'Problem Solving/LeetCode' Related Articles more
Comments