Number of Paths in Rectangular Grid
Source: Solved it during Algorithms Course under Prof Diwan, and discussed with Nikhil Jain (IT BHU 2008 Alumnus, Product Manager at AskLaila)
Consider a n x m rectangular grid. The problem is to find the number of shortest (or monotonic in this case) paths along the edges of the cell that start at (0,0) and end at (n,m).
A monotonic path is a path always moving towards the goal, i.e. consists of moving up or right but not down or left. Figure 1 illustrates such a path for a grid of size 5 x 3.
Now we need to print all monotonic paths that do not go above the diagonal y = x. Figure 2 shows such a path. Note that the path in figure 1 goes above the diagonal, hence not desirable in this case. How many such paths exist for n x m grid (n >= m)?
The first problem is too simple, and the second is very challenging. Have fun :-)