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?
Solution:
int help(int m, int n, vector<vector<int> >& result)
{
if(result[m][n]!=-1)
{
return result[m][n];
}
result[m][n] = 0;
if(m>1)
result[m][n] += help(m-1,n,result);
if(n>1)
result[m][n] += help(m,n-1,result);
return result[m][n];
}
int uniquePaths(int m, int n) {
vector<vector<int> > result(m+1, vector<int>(n+1, -1));
result[1][1] = 1;
help(m, n, result);
return result[m][n];
}
No comments:
Post a Comment