62 Unique Paths

A robot is located at the top-left corner of amxngrid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note :m and n will be at most 100.

Approach 1: Brute Force

The Idea: One solution is to look options we have available at every cell (i,j). Since we have the option to only move down or right this simplifies the problem. For example, if we are in row 2, and there are 3 rows, then we only have the option to move down another row. Likewise, if we are on the 4th column and there are total of 7 columns, then we can move to the right 3 more places. In general, the cell we are under will provide us with available options we have left. Finally, the available paths can summarizes as the root to leaf paths, and the total number of paths are then just the number of leaves. There some obvious improvements here, but the purpose was just to demonstrate a brute force approach.

Complexity: O(2^n) time and O(2^n) space

import queue

class Node:
    def __init__(self, count_D, count_R):
        self.count_D = count_D
        self.count_R = count_R
        self.D = None
        self.R = None


class Solution:

    def __countNumLeaves(self, root):
        """
        :param root: Node
        :return: int
        """
        if root is not None:
            if root.D is None and root.R is None:
                return 1
            return self.__countNumLeaves(root.D) + self.__countNumLeaves(root.R)
        return 0

    def uniquePaths(self, rows, cols):
        """
        :type m: int
        :type n: int
        :rtype: int
        """

        q = queue.Queue()
        root = Node(rows-1, cols-1)
        q.put(root)

        while not q.empty():
            front = q.get()
            if front.count_D > 0:
                front.D = Node(front.count_D-1, front.count_R)
                q.put(front.D)
            if front.count_R > 0:
                front.R = Node(front.count_R-1, front.count_D)
                q.put(front.R)

        return self.__countNumLeaves(root)

Approach 2: Dynamic Programming

The Idea: A better approach would be to try and identify the relationship between the cells as the matrix grows larger. Since we can only move down and right, the total number of paths are simply the number of ways that are approached from the left and above.

Complexity: O(n*m) time and space. Space can actually be improved to be linear because if you think about it, the only cells we are interested in are the previous cells from above and to the right - and as long as we maintain a previous vector that consistently gets updated, we are good.

int uniquegrids(int m, int n) {
    vector<vector<int> > grid(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
    return grid[m - 1][n - 1];
}