DP is easy — Part-6

4 min readAug 12, 2020

“Measuring programming progress by lines of code is like measuring aircraft building progress by weight.” — Bill Gates

Hey reader! Hope you had all had a good time with the previous blog in which we learnt the advance variant of ‘take it or leave it’ principle. From now on-wards our focus would be on solving few common C.P. and interview problems related to grids. So roll-up your sleeves and get ready to include this awesome DP technique in your algorithmic armory.

Let’s start with the discussion

Today we would be solving Grid-1 problem from AtCoder Educational DP contest. The problem states that “We have n*m grid where each cell is either free (represented by ‘.’ ) or blocked (represented by ‘#’). We can either move right (i.e. from ( i ,j ) we can go ( i ,j+1 )) or move down(i.e. from cell ( i, j) we can go to ( i+1,j)). Find the total number of ways to reach cell (n-1,m-1) starting from (0,0) modulo 10⁹ + 7”.

Constraints : 1≤n,m≤1000;

You can read the problem statement from here, for further clarifications.

Let’s start solving

STEP 1 — Build a naive recursive solution

Suppose we are at a cell ( i , j ) which is free. The number ways to reach this cell would be nothing but the summation of the number of ways to reach cell (i-1, j) and cell (i , j-1), since we could only come from either the cell just above our current cell or from the cell to the left of our current cell.

The above recurrence can be written as:

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

So, to get our final answer we just have to call the function starting from the cell (n-1,m-1). We just have reversed the way we are solving the problem(i.e. rather than finding number of paths from (0,0) to (n-1,m-1) we are finding the number of paths from (n-1,m-1) to (0,0)).

Let’s see what all base cases we have :

If we reach our destination cell i.e. ( 0,0 ) return 1( this one indicates that there exist 1 path using which we reached the destination cell; the number of times we reach (0,0) is simply the total number of unique paths ).
If we reached a blocked cell, return 0; since there is no path using which we can reach this cell.
If we try to move to any invalid position (i.e. outside our grid ) return 0.

Let’s see a recursive code made from the above discussion.

Follow the simple formula master recursion to master DP.

Time Complexity : O(2^(n+m)) ( Since at each cell we have to take summation of paths from left or up. In worst case this complexity would go up-to 2²⁰⁰⁰ )

STEP 2 — Memoize the recursive solution

By now, if you would have been following my previous blogs you must have guessed how our memoization table will look like. For those, who are new here goes the explanation.

Look at the changing parameters in each function call, they are none other than row, col which indicates current row and current column respectively. So, if we somehow make a memoization table keeping a record of all row, col value we would be done.

Here is the memoized code for our problem;