Indian Computing Olympiad

Dynamic Programming

Counting paths in a grid

You have a rectangular grid of points with n rows and n columns. You start at the bottom left corner. At each step, you can either go up to the next point in the same column or right to the next point in the same row. How many such paths are there from the bottom left corner to the top right corner?

Solution

We have to take 2n steps, of which we have to choose n to be up moves and n to be right moves. This gives (2n choose n) paths.

Instead, we can use a recursive formulation:

• Path(i,j) : No of ways of going from origin to (i,j)
• Path(i,j) = Path(i-1,j) + Path(i,j-1)
  
  i.e. Any path to (i,j) comes via (i-1,j) or (i,j-1) and no path can come via both these routes, so we can recursively solve the problems for these two predecessor points and add them.
• Boundary conditions:
• Path(i,0) = 1
• Path(0,j) = 1

This is a recurrence relation. Solving this naively is inefficient, because Path(i,j) will be recomputed several times.

Instead, start at bottom left corner and compute the values along diagonals with points (i,j) where i+j is constant. Write a loop to store these values in an array. Takes time proportional to n*n (each grid point is updated exactly once and read upto twice).

One way to structure the solution as a simple nested loop is:

       for c = 0 to n*n
         for each (i,j) such that i+j = c
           update Path(i,j) using Path(i-1,j) and Path(i,j-1)
      

This way, whenever a new value Path(i,j) has to be computed, the values it depends on --- Path(i-1,j) and Path(i,j-1) --- are already known.

Why is the recursive solution better?

What if some points are deleted (that is, no path can go through these points)?

If there is one deleted point, we have to subtract the number of paths that pass through these points.

In general, holes may be arbitrarily complicated: if we have two holes, we subtract number of paths that pass through either hole, but we have then subtracted twice the paths that go through both holes, so we have to add these back.

Instead, we can modify the recurrence to take into account the holes.

• Path(i,j) = Path(i-1,j), if (i-1,j) connected to (i,j)
                    + Path(i,j-1), if (i,j-1) connected to (i,j)
• Path(i,0) = 0 or 1, depending on whether there is a hole between (0,0) and (i,0)
• Path(0,j) = 0 or 1, depending on whether there is a hole between (0,0) and (0,j)

Video lecture on Grid paths, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)