Related Tags

lattice path
north east

# What are lattice paths?

A lattice path is composed of horizontal and vertical lines that pass through lattice pointsPoints at the intersection of two or more gridlines in a regularly spaced array of boxes..

A lattice path, across a 6x6 grid that starts at the origin and allows only North and East movements, is shown below.

Remember: Diagonal movements are not allowed in this example, only North and East movements.

The total number of paths from the origin (0,0) to a point (a,b) that is restricted to the North and East directions only can be found using the binomial coefficient ${a+b}\choose{a}$.

1 of 2

## Code

This problem can be solved using dynamic programming. Take the base case where there is a grid of 1x1 and there are exactly $2$ solutions. In a 2x2 grid, there are $6$ ways, $2$ previous paths, and 1 additional path for each direction: $(2+1)$ x $2$. If we generalize the idea, the total number of paths is the sum of the previous paths on the left and the top. The diagonal follows the series $1,2,6,20,70,252,924$, which are all middle elements of Pascal's Triangle. This is similar to ${2a}\choose{a}$.

Here is the solution:

#include <iostream>
using namespace std;

//function to calculate paths
int paths(int n){
// apply the above stated rule for n iterations
int j = 1;
for (int i= 1; i <= n; i++)
{
j = j * (n + i) / i;
}
return j;
}

int main() {
// input grid size
int p = paths(0);

//print paths
cout << "The number of paths are: "<< p << endl;
return 0;
}

RELATED TAGS

lattice path
north east