leetcode, 62. Unique Paths

up.py

class Solution:
    def uniquePathsBruteForce(self, m: int, n: int) -> int:
        grid = [[""] * m for _ in range(n)]

        def up(grd):
            if len(grd) == 0:
                return 0
            # the last cell
            elif len(grd) == 1 and len(grd[0]) == 0:
                return 1
            # the last column
            elif len(grd) > 1 and len(grd[0]) == 1:
                return 0 + up(grd[1:])
            # the last row
            elif len(grd) == 1 and len(grd[0]) > 1:
                right_grid = [i[1:] for i in grd]
                return 0 + up(right_grid)
            else:
                right_grid = [i[1:] for i in grd]
                return up(right_grid) + up(grd[1:])

        return up(grid)

    def uniquePaths(self, m, n):
        grid = [[1] * m for _ in range(n)]

        for i in range(1, n):
            for j in range(1, m):
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
        return grid[n - 1][m -1]