Skip to content

Instantly share code, notes, and snippets.

@m-khooryani
Created July 2, 2020 09:30
Show Gist options
  • Save m-khooryani/451f93eeb549c70430288d9b6dc8d933 to your computer and use it in GitHub Desktop.
Save m-khooryani/451f93eeb549c70430288d9b6dc8d933 to your computer and use it in GitHub Desktop.
Count Paths in n*m Matrix (DP)
This problem was asked by Facebook.
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.
static void Main(string[] args)
{
int n = 5, m = 5;
Console.WriteLine(CountPaths(n, m)); // 70
}
static int CountPaths(int n, int m)
{
int[,] dp = new int[n, m];
dp[n - 1, m - 1] = 1;
for (int i = n - 1; i >= 0; i--)
{
for (int j = m - 1; j >= 0; j--)
{
if (i + 1 < n)
{
dp[i, j] += dp[i + 1, j];
}
if (j + 1 < m)
{
dp[i, j] += dp[i, j + 1];
}
}
}
return dp[0, 0];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment