[leetcode][62] Unique Paths

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

---

 

학창시절 때 배웠던 것을 떠올려본다.

3*4 그리드가 있다고 하면

일단 가장 위에 행과 가장 왼쪽 행은 1로 갱신한다. 

이 부분들은 갈 수 있는 횟수가 전부 1이다. (오른쪽으로만 가거나 아래로만 가거나)

 

남은 그리드 부분은 왼쪽+위가 갈 수 있는 경우의 수가 된다.

(위에서 내려오거나, 왼쪽에서 오른쪽으로 오거나)

 

이렇게 왼쪽 위에서부터 오른쪽 아래 방향으로 차례대로 모든 그리드를 채웠을 때

가장 오른쪽 아래에 있는 수(10)가 정답이 된다.

 

시간복잡도는 O(NM).

 

---

소스코드 

C++ : https://gist.github.com/fpdjsns/7640cc2431977f51ce86007374ddf8e5

pythone : https://github.com/fpdjsns/Algorithm-python/blob/main/leetcode/medium/62.%20Unique%20Paths.py