A mathematical solution in O(n+m), C++


  • 1
    R

    This problem is a classical combinatorics problem. The solution is combinaton(n+m, n).

    int uniquePaths( int m, int n )
    {
    	if ( m == 1 || n == 1 )
    		return 1;
    	m--; n--;
    	double factorial_n = 1, factorial_mn = 1;
    	for ( int i = 2; i <= n; ++i )
    		factorial_n *= i;
    	for ( int i = m + 1; i <= m + n; ++i )
    		factorial_mn *= i;
    	return int( factorial_mn / factorial_n );
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.