목록Dynamic Programmin (1)

개발자가 되고 싶은 준개발자

[LeetCode] 64. Minimum Path Sum 풀이 및 코드

문제 왼쪽 상단 코너에서 오른쪽 하단 코너까지 각 칸에 적힌 수의 합이 최소인 경로를 구해라. 풀이 이 문제를 푸는 데 중요한 포인트는 특정 칸까지의 최소인 경로는 하나만 구하면 된다는 점이다. 그 경로가 어떤 경로인지는 중요하지 않고, 수의 합이 최소라는 점만 중요하다. 따라서 최소의 합을 내는 경로를 구했다면 그 최소의 합만 저장하고, 경로는 저장할 필요가 없다. 따라서 이 문제는 동적 프로그래밍으로 풀기에 적합하다. 각 칸까지의 경로의 최소 합을 저장하고, 다음 칸의 값을 구할 때 이전 값들을 사용하면 된다. 즉, dp[i][j] = min(dp[i-1][j], dp[i][j-1])+ grid[i][j]. (물론, 예외처리는 해주어야 한다.) 코드 class Solution(object): def ..
알고리즘 공부/LeetCode 2020. 9. 19. 21:28
이전 Prev 1 Next 다음