leetcode Question 116: Unique Path I

Unique Path I

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?

Analysis:

This is an easy problem. From the description we know that, the robot can only move down or right, which means, if the robot is now in position (x,y), then the position before this step must be  either (x-1,y) or (x, y-1). Since current position is only from these two previous positions, the number of possible paths that the robot can reach this current position (x,y) is the sum of paths from (x-1, y) and (x, y-1).

We want to get the number of paths on position (m,n), we need to know (m-1,n) and (m, n-1). For (m-1,n), we must know (m-2,n) and (m-1,n-1) ...  until we back to the start position (1,1) ([0][0] in  C++). Note that the boundary of the map, we can easily know that the top row and the first column of the map are all 1s. Use loop can solve the problem then.

Code(C++):

class Solution {
public:
    int uniquePaths(int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int **arr = new int* [m];
        for (int i=0;i<m;i++){
            arr[i]= new int[n];
        }
        arr[0][0]=1;
        for (int i=0;i<m;i++){
            arr[i][0] = 1;
        }
        for (int i=0;i<n;i++){
            arr[0][i] = 1;
        }
        for (int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                arr[i][j] = arr[i][j-1] + arr[i-1][j];
            }
        }   
        return arr[m-1][n-1];
    }
};

Code(Python):

class Solution:
    # @return an integer
    def uniquePaths(self, m, n):
        #define map and initialization
        mp = [[0 for i in xrange(n)] for i in xrange(m)] 
        for i in xrange(m):
            mp[i][0]=1
        for j in xrange(n):
            mp[0][j]=1
        
        for i in xrange(1,m):
            for j in xrange(1,n):
                mp[i][j]=mp[i-1][j]+mp[i][j-1]
                
        return mp[m-1][n-1]