본문 바로가기
알고리즘 문제/Leetcode

[Leetcode][931] Minimum Falling Path Sum

by 햄과함께 2018. 12. 18.
320x100

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




DP로 풀었다.

떨어지는 경로의 배열 합이므로 현재 위치에서 갈 수 있는 배열은 왼쪽 아래, 아래, 오른쪽 아래이다.

따라서 점화식은 아래와 같이 만들 수 있다.


d[i][j] = A[i][j] + min(d[i-1][j-1], d[i-1][j], d[i-1][j+1])
cs


배열을 모두 돌며 배열 d를 채웠을 때 마지막 행에서 가장 작은 값이 정답이 된다.


시간복잡도는 A배열이 NxN이라 했을 때, O(N^2).




소스코드 : https://gist.github.com/fpdjsns/18f4d32c49ac294a4175065fc8cfca90

320x100

댓글