# Unique Paths

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n for _ in range(m)]
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
        
        return dp[m-1][n-1]

"""
걸린 시간: 10분

복잡도: 격자판의 모든 칸을 한번씩 갱신하기 때문에 시간복잡도와 공간복잡도 둘 다 O(nm)이다.

해설: 목적지는 오른쪽 아래 끝이고, 움직이는 방법도 오른쪽으로 가거나 왼쪽으로 가거나 두 가지 방법밖에 없다.
따라서 첫번째 행부터 쭉 채워나가는 방식으로 진행하면 이미 갱신한 칸으로 다시 돌아올 이동 방법이 없기 때문에 그것이 그 칸에 가는
최종 경우의 수가 된다.
갱신하는 방법은 현재 보는 칸으로 올 수 있는 이전 칸의 경우의 수를 더하는 것인데, 윗칸과 왼쪽 칸의 경우의 수를 더하면 된다.
"""