Leetcode: Unique Paths

Unique Paths | LeetCode OJ

This is just like the finonacci series calculation using dynamic programming. Fibonacci series is in one dimension here we have a two dimensional grid.

1. The first node need to be marked 1.
2. Only one path is available for points along the first row and first column. Take care of it in the initialization and omit them while traversal
3. Number of paths reaching a given point is the sum of paths reaching the point above it and the point to the left of it
4. Store the results in a dictionary to avoid re-computation

Remarks:

1. O(m*n) time complexity
2. O(m*n) space complexity
3. Try printing the solution for a 3 x 3 grid, you will see a familiar pattern.

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[1] * n] * m
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        return dp[-1][-1]