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?

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

Note: m and n will be at most 100.

C++:
01 class Solution {
02 public:
03     int uniquePaths(int m, int n) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         vector<int*> A(m);
07         for(int i=0;i<m;i++)
08         {
09             A[i]=new int[n];
10             for(int j=0;j<n;j++)
11             {
12                 A[i][j]=0;
13             }
14         }
15         for(int i=1;i<m;i++)
16         {
17             A[i][0]=1;
18         }
19         for(int i=0;i<n;i++)
20         {
21             A[0][i]=1;
22         }
23         for(int i=1;(i<m)&&(i<n);i++)
24         {
25             A[i][i]=A[i1][i]+A[i][i1];
26             for(int j=1;j+i<n;j++)
27             {
28                 A[i][i+j]=A[i1][i+j]+A[i][i+j1];
29             }
30             for(int j=1;i+j<m;j++)
31             {
32                 A[i+j][i]=A[i+j1][i]+A[i+j][i1];
33             }
34         }
35         return A[m1][n1];
36     }
37 };
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