Problems Involving Grids - 2

Problem statement

The problem in this lesson tries to solve the following type of question:

Finding the number of ways to reach from a starting position to an ending position when traveling in specified directions only.

The problem statement is:

Given a 2-D matrix with M rows and N columns, find the number of ways to reach the cell with coordinates (i, j) from the starting cell (0, 0) under the condition that you can only travel one step right or one step down.

This problem is very similar to the previous one. To reach a cell (i, j), one must first reach either the cell (i-1, j) or the cell (i, j-1), and then move one step down or to the right respectively to reach cell (i, j).

Solution: Dynamic programming approach

This problem indeed satisfies the optimal substructure and overlapping subproblems properties, so we need to try and formulate a dynamic programming solution.

Let numWays(i, j) be the number of ways to reach position (i, j). As stated above, the number of ways to reach cell (i, j) will be equal to the sum of the number of ways of reaching (i-1, j) and the number of ways of reaching (i, j-1). Thus, we get the following recurrence relation:

numWays(i, j) = numWays(i-1, j) + numWays(i, j-1)

Let’s move to the implementation now.