Count Paths in n*m Matrix (DP)

README.txt

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.

Program.cs

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];
}