[leetcode] unique-paths - Python

문제링크
https://leetcode.com/problems/unique-paths/submissions/1179788926/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제풀이

 

m x n 크기의 grid에 로봇이 오른쪽이나 아래로만 이동합니다.

이때 가장 오른쪽 아래지점 즉 (m-1, n-1)지점으로 가는 모든 경우의 수의 path를 구하는 문제입니다.

 

먼저 맨위에 행과 맨왼쪽의 열은 무조건 하나의 경우의 수밖에 없으니까 1로 지정을 해주었습니다.

 

그런다음에 지정되지 않은 구역부터 for문으로 탐색을해 위의 경우 ( i -1, j)와 왼쪽의 경우(i, j-1)의 수를 더해주어서 마지막으로 맨 마지막 구역을 return 해주었습니다.

 

풀이코드

 

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # grid를 만들어서 초기는 전부 1로 해준다
        # 1행과 1열을 전부 1로해준다
        grid = [ [False] * n for _ in range(m)]
        
        memo = {}

        for i in range(m):
            memo[(i,0)] = 1
        for j in range(n):
            memo[(0,j)] = 1
        

        for i in range(1,m):
           for j in range(1,n):
               memo[(i,j)] = memo[(i-1,j)] + memo[(i,j-1)]

        return memo[(m-1,n-1)]