Unique Paths : Part 1

Problem Description
A robot is located at the top-left corner of a m x n grid (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.

Solutions:
This is a typical problem using dynamic programming. However, this problem is the first level of dynamic programming problems! All you need is to find out the recursive relation, and implement it!
NOTE: small m & n would suggest us that this is a dynamic programming problem. However, since m & n are too small, it suggests that we can solve the problem using another method! Let's look at the 3rd solution for it ^_^
I. Simple Solution

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        a = [[0] * (n+2) for i in range(m+1)]
        
        for i in range(1, n+1):
            a[m][i] = 1
        for i in range(1,m):
            for j in range(0,n):
                a[m-i][n-j] = a[m-i+1][n-j] + a[m-i][n-j+1]
                
        return a[1][1]

II. Improvement on Solution time & Space Complexity
In this solution, we use less space than the above solution.

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        a = [ 1 for i in range(n)]
        
        for j in range(1, m):
            for i in range(1,n):
                a[i] += a[i-1]
        return a[n-1]

III. Combinatoric Solution
We see that the robot is standing at location (1,1), and it wants to move to location (m,n). So in total, it needs to move (m-1) steps downwards, and (n-1) steps rightwards, in any orders! If we mark going down as 1, and going to the right as 0, we have a string of length (m+n-2) which consists of 1 and 0. So you guess it, there are how many strings like that? Yes, it is (m+n-2)!/[(n-1)!*(m-1)!]

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        # we assume m, n >= 1
        if m == 1 or n == 1: return 1
        
        m -= 1
        n -= 1
        if m > n:
            t = m
            m = n
            n = t
        
        result = 1
        for i in range(1,m+1):
            result *= (n + i)
            result /= i