c++ - Count all possible paths from top left to bottom right of a mXn matrix

Question

I should return number of possible paths from top left to bottom right in an n*m matrix. here is my code.

class Solution {
 public:
 map<pair<int,int>,long long int>mp;
   long long int numberOfPaths(int m, int n){
       if(n==1 || m==1)
       {
           return 1;
       }
       if(mp[make_pair(n,m)]!=0)
       return mp[make_pair(n,m)];
       mp[make_pair(n,m)]=numberOfPaths(n-1,m)+numberOfPaths(n,m-1);
       return mp[make_pair(n,m)];
   }
};

i got many solutions for this problem but i am interested in finding whats wrong in my code. And i got wrong answer for input 19 and 71.

question from:https://stackoverflow.com/questions/65949241/count-all-possible-paths-from-top-left-to-bottom-right-of-a-mxn-matrix

Answer 1

Short answer: Your expected answer is wrong. The correct answer for input 19 and 71 is indeed 2418561960739869780.

Long answer:

Firstly, always keep code formatted - it helps yourself and the reader of such questions gather some motivation to read the question. Here is a slightly better formatted version:

class Solution {
public:
    map<pair<int, int>, long long int> mp;
    long long int numberOfPaths(int m, int n) {
        if(n == 1 || m == 1) {
            return 1;
        }
        if(mp[make_pair(n, m)] != 0) return mp[make_pair(n, m)];
        mp[make_pair(n, m)] = numberOfPaths(n-1, m) + numberOfPaths(n, m-1);
        return mp[make_pair(n, m)];
    }
};

Secondly, always try and include reproducible code. When you only share a class definition, it will be hard for the reader to understand how you are using it.

Thirdly, I understand you are doing this as part of dynamic programming. But this approach is brute-force (as pointed in an earlier comment already). The mathematical solution to this is (m-1) + (n-1) C (m-1) since you have as many combinations. This computes faster as well since multiplication instead of repeated addition is optimised.

88 C 18 is indeed 2418561960739869780.