Unique Paths

Dynamic Programming
Medium

Approach

Diagrams

Analysis

Time

O(mn)

Space

O(mn)
class Solution:
    def uniquePaths(self, numRows, numCols):
        dp = self.buildDP(numRows, numCols)

        for row in range(1, numRows):
            for col in range(1, numCols):
                dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

        return dp[-1][-1]

    def buildDP(self, numRows, numCols):
        dp = [[0 for col in range(numCols)] for row in range(numRows)]

        for row in range(numRows):
            dp[row][0] = 1

        for col in range(numCols):
            dp[0][col] = 1

        return dp

Learn

#Dynamic Programming

Videos