Sunday, May 5, 2013

Leetcode: Unique Paths in C++



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