[알고리즘][DP] - unique path

[문제]

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

Unique Paths - LeetCode

- 해당 문제는 조합을 이용해서 풀이가 가능하다.

- 조합을 사용하게 되면 해당 문제에 변수를 주었을 때 해결하기 어려워진다.

- 위에서 아래로 왼쪽에서 오른쪽으로만 갈수 있기 때문에 조합으로 풀수 있다.

  - m = 2(세로), n = 5(가로)라고 할 때 아래로는 1번만 내려가면 되고 오른쪽으로는 4번만 가면 오른쪽 맨 아래 도착지점에 도달할 수 있기 때문이다. 

 

[문제 해설]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        memo = [[-1] * n for _ in range(m)]

        def dfs(r,c):
            if r == 0 and c == 0:
                memo[r][c] = 1
                return memo[r][c]
            unique_path = 0
            if memo[r][c] == -1:
                if r-1 >= 0:
                    unique_path += dfs(r-1, c)
                if c-1 >= 0:
                    unique_path += dfs(r, c-1)
                memo[r][c] = unique_path
            return memo[r][c]

        return dfs(m-1, n-1)

m = 2, n = 3인 경우? 

1	1	1
1	2	3

• dp table은 이런 식으로 채워지게 된다.