[Leetcode][931] Minimum Falling Path Sum

문제 : 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])

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

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

---

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