931. Minimum Falling Path Sum

931. Minimum Falling Path Sum

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

문제

풀이

문제 설명에는 명시되어 있지 않으나 알아야 할 조건이 있다.
1. col == 0(맨 왼쪽에 있을 때) => (row+1, col), (row+1, col+1)로 갈 수 있다.
2. col == len(matrix)-1(맨 오른쪽에 있을 때) => (row+1, col), (row+1, col-1)로 갈 수 있다.
3. 이 외에는 (row+1, col), (row+1, col-1), (row+1, col+1)로 갈 수가 있다.
4. 종료조건에는 당연히 맨 아래에 있을 때 len(matrix) -1일 때에 값을 리턴해주면 된다.
5. 재귀구조이기 때문에 불필요한 연산이 있을 수 있으므로 Cache를 이용하여 존재하는 값은 캐쉬에서 리턴한다.
6. DFS로 조건에 맞는 경우의 수를 찾고 그 중 최소값만 Cache에 저장하게 한다.

결과