LeetCode_62. Unique Paths

leetcode.com/problems/unique-paths/

Unique Paths - LeetCode

Solution1. 

 

M x N 사이즈의 table을 이용,

 

(r,c) 칸으로 이동할수 있는 경우는 바로 위에칸(r-1,c)에서 아래로 이동하거나 왼쪽 칸(r,c-1)에서 오른쪽으로이동하는 경우만 존재 함, 따라서 (r,c)까지 이동 할수 있는 경우의 수는 아래와 같이 표현 가능하다.

 

table[r][c] = table[r-1][c] + table[r][c-1]

                    Down           Right

 

또한 r=0 인 모든 column과 c=0인 모든 row의 이동 가능한 경우는 1가지 밖에 없으므로  table의 초기화 값을 1로 하고 for문은 (1,1) 부터 시작하여 table을 완성 하는 기초적인 DP문제

 

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        table = [[1]*m]*n
        
        for r in range(1, n):
            for c in range(1, m):
                
                table[r][c] = table[r][c-1] + table[r-1][c]
                
        return table[-1][-1]