Unique paths

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?

C++:
01 int unique_path(int m, int n)
02 {
03     int i,j;
04     vector <int*> A(m);
05     for(i=0;i<m;i++){
06         A[i]=new int[n];
07     }
08     for(i=0;i<m;i++){
09         for(j=0;j<n;j++)
10             A[i][j]=0;
11     }
12     for(i=0;i<m;i++)
13         A[i][n1]=1;
14     for(j=0;j<n1;j++)
15         A[m1][j]=1;
16     for(i=m2;i>=0;i){
17         for(j=n2;j>=0;j){
18             A[i][j]=A[i+1][j]+A[i][j+1];
19         }
20     }
21     return A[0][0];
22 }
Advertisements
This entry was posted in Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s