목록Minimum Path Sum (1)

m1ndy5's coding blog

LeetCode 64. Minimum Path Sum with Python

https://leetcode.com/problems/minimum-path-sum/description/  bfs로 접근했다가 시간초과가 났던 문제생각해보니까 그럼 앞서 갔던 길들을 최적으로 다시 다 바꿔줘야해서 bfs를 사용하면 안된다는 생각이 들었다.그러다 생각이 든게 어짜피 오른쪽, 아래쪽으로밖에 움직이지 않으니까위 한줄, 왼쪽 한줄의 비용을 미리 계산해놓고 위에서 오는게 cost가 적은지 왼쪽에서 오는게 cost가 적은지 판단하면 된다고 생각했다. class Solution(object): def minPathSum(self, grid): """ :type grid: List[List[int]] :rtype: int """ # ..
알고리즘 with python/20240909 2024. 10. 11. 10:07
이전 Prev 1 Next 다음