[백준][다이나믹] 1520 내리막길

내리막길은 DFS와 DP를 혼합하여 해결할 수 있는 문제이다. 

DFS를 이용하여 종점을 찾아서 

다시 돌아오면서 DP로 현재 경로에서 종점으로 갈 수 있는 경우를 메모한다. 

이미 메모한 곳을 찾으면 해당 값을 반환하면 된다. 

  * -1로 초기화 하여, 방문한 곳을 0으로 표시하면 다시 방문하지 않아도 된다. 

최종 위치에서 되돌아 가면서 경로를 표시하고, 

새로운 경로로 가면서 최종 위치로 도달할 수 있는 경로를 만나면 그값을 더하여 처리한다. 

<테스트 케이스>

10 10

20 19 18 17 16 15 14 13 12 11 

19 18 17 16 15 14 13 12 11 10 

18 17 16 15 14 13 12 11 10  9 

17 16 15 14 13 12 11 10  9  8 

16 15 14 13 12 11 10  9  8  7 

15 14 13 12 11 10  9  8  7  6 

14 13 12 11 10  9  8  7  6  5 

13 12 11 10  9  8  7  6  5  4 

12 11 10  9  8  7  6  5  4  3 

11 10  9  8  7  6  5  4  3  2 

https://www.acmicpc.net/problem/1520