Leetcode_by_Python/062_UniquePaths.py at main · 4daJKong/Leetcode_by_Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def uniquePaths_combination(self, m: int, n: int) -> int:
        res = 1
        prod1 = 1
        prod2 = 1
        for i in range(m - 1, 0, -1):
            prod1 = prod1 * i
        for j in range(m + n -2, n - 1, -1):
            prod2 = prod2 * j
        res = prod2/prod1
        return int(res)

    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for i in range(m)] for j in range(n)]
        for i in range (1, n):
            for j in range(1, m):
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[n - 1][m - 1]


print(Solution().uniquePaths(m = 3, n = 7)) #28
print(Solution().uniquePaths(m = 3, n = 2)) #3
print(Solution().uniquePaths(m = 7, n = 3)) #28
print(Solution().uniquePaths(m = 3, n = 3)) #6