62. Unique Paths

62. Unique Paths

https://leetcode.com/problems/unique-paths/

문제

풀이

DFS 트리 구조로 나타내면 다음과 같다.
조건 중에서 down, right로만 갈 수 있다고 명시하였고, row가 m-1보다 크면 안되고(up을 할 수 가 없다.) col이 n-1보다 크면 안된다.(left를 할 수가 없다.)

즉 row가 m-1이고 col = n-1이면 도착했다는 말이므로 1을 리턴한다. cnt_row, cnt_col으로 나눈 이유는 오른쪽으로 가는길, 밑으로 가는 길 2가지가 있기 때문에 2개를 더해주고 그 값을 캐시에 저장한다. 따라서 재귀구조때 불필요한 계산을 줄일 수 있다.

결과