## 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]

I think most of your posts are great but sometimes it is very hard to understand your English though.

ReplyDeleteActually I have been refining both the analysis and code in all my posts recently. Thank you very much for your suggestion.

DeleteDoes this algorithm have a name?

ReplyDeleteDoes this algorithm have a name?

ReplyDeleteDynamic Programming

DeleteI LOVE YOU YU!

ReplyDeletewhy did you initialise by 1 for the borders ?

ReplyDelete