62. Unique Paths - python3

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

도저히 감도 못잡겠고 두통이 오는 것 같아.. 답을 봤읍니다^^

DP solution

Solution 1: Runtime: 24 ms - 95.81% / Memory Usage: 14.2 MB - 46.26%

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[None for _ in range(n)] for _ in range(m)] # Empty dp table
        k = min(m,n)
        for d in range(k):
            # Vertical line
            if d == 0:
                for i in range(d,m):
                    dp[i][d] = 1
                for j in range(d,n):
                    dp[d][j] = 1
            else:
                for i in range(d,m):
                    dp[i][d] = dp[i - 1][d] + dp[i][d - 1]
                for j in range(d,n):
                    dp[d][j] = dp[d - 1][j] + dp[d][j - 1]
            #print(dp)
        return dp[m - 1][n - 1]

(i, j) 의 위, 왼쪽 값의 합이 들어가는데 신기하게도 답이 나온다

이건 Dynamic Programming 동적 계획법이라고 한다.
점화식을 이용.
이거도 알아두면 좋을 듯

동적 계획법 알고리즘 문제풀이 기초와 예제
참고: https://www.leafcats.com/72

Math solution - Binomial Coefficient 이항 계수

Solution 2: Runtime: 112 ms - 5.28% / Memory Usage: 42.4 MB - 5.07%

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Binomial coefficient solution
        import scipy.special
        return int(scipy.special.binom(m + n - 2, m - 1))

이항 계수를 이용하면 된다고도 하네요~...

[조합론] 이항계수 알고리즘 3가지
참고: https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

이런게 있다고 함... 첨보는 느낌