[Algorithm] LeetCode 62 - Unique Paths in Python(파이썬)

💡 LeetCode 62:

m * n 배열에서 (0, 0) 부터 시작하여 (m-1, n-1)까지 도달하는 경우의 수 DP 탐색
이동은 오른쪽 또는 아래 방향으로만 움직인다

🌱 코드 in Python

알고리즘: Dynamic Programing

class Solution(object):
    def uniquePaths(self, m, n):
        dp = [[1] * n for i 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]

처음 문제를 보고 모든 경우의 수를 구해야 한다고 생각해서
dfs나 brute force로 접근해야 한다고 생각했다.

그러나! 이 문제의 경우 이동 방향이 제한되어 있고, 목적지 또한 일정하므로
DP로 충분히 해결할 수 있는 문제였다!

방문처리가 필요하지도 않고, 해당칸에 도달할 수 있는 경우의 수를 계속해서 갱신해 나가면 딘다.

🧠 기억하자

1. 문제를 잘 읽고 적절한 풀이 방식을 고를 수 있도록 하자!

LeetCode 62 바로가기