Created
July 2, 2020 09:30
-
-
Save m-khooryani/451f93eeb549c70430288d9b6dc8d933 to your computer and use it in GitHub Desktop.
Count Paths in n*m Matrix (DP)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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