Count number of ways to reach bottom right corner from top left corner

There is an N by M matrix of zeroes. Given N and M, write a function to count the number of ways of starting at the top-left corner and getting to the bottom-right corner. You can only move right or down.

For example, given a 2 by 2 matrix, you should return 2, since there are two ways to get to the bottom-right:

• Right, then down
• Down, then right

Given a 5 by 5 matrix, there are 70 ways to get to the bottom-right.

Example:

Input:  n = 5, m = 5
Output: 70

Approach

C++

#include <bits/stdc++.h>
using namespace std;

//count unique path from
//top left corner to bottom
//right corner
int uniquePaths(int m, int n)
{
    //base case
    if (m == 0)
        return 0;
    int dp[m][n];
    for (int i = 0; i < m; i++)
        dp[i][0] = 1;
    for (int i = 0; i < n; i++)
        dp[0][i] = 1;
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}
int main()
{
    int m = 5, n = 5;
    cout << uniquePaths(m, n);
    return 0;
}