number-of-unique-paths.md

Number of Unique Paths

Given a A X B matrix with your initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position.

Note: Possible moves can be either down or right at any point in time, i.e., we can move to matrix[i+1][j] or matrix[i][j+1] from matrix[i][j].

Sample Input

4 4

Sample Output

20

Solution

class Solution
{
    public:
    int NumberOfPath(int a, int b)
    {
        vector<vector<int>> M(a, vector<int>(b, 1));
        
        for(int r = 1; r < a; ++r) {
            for(int c = 1; c < b; ++c) {
                M[r][c] = M[r-1][c] + M[r][c-1];
            }
        }

        return M.back().back();
    }
};

Accepted