Yuan
0%

62. Unique Paths

Posted on

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

Solution1: top down dp

1
2
3
4
5
6
7
class Solution:
    @cache
    def uniquePaths(self, m: int, n: int) -> int:
        if m==1 or n==1:
            return 1
        elif m>1 and n>1:
            return self.uniquePaths(m-1,n)+self.uniquePaths(m,n-1)

Solution2: bottom up dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        """
        assume we have solved P(i-1,j) and P(i,j-1)
        then P(i,j)=P(i-1,j)+P(i,j-1)
        """
        P=[[0]*n for _ in range(m)]
        for i in range(n):
            P[0][i]=1
        for j in range(m):
            P[j][0]=1
        for i in range(1,m):
            for j in range(1,n):
                P[i][j]=P[i-1][j]+P[i][j-1]
        return P[m-1][n-1]