Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

lattice path
north east

What are lattice paths?

Educative Answers Team

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.

svg viewer

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+ba){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 22 solutions. In a 2x2 grid, there are 66 ways, 22 previous paths, and 1 additional path for each direction: (2+1)(2+1) x 22. 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,9241,2,6,20,70,252,924, which are all middle elements of Pascal's Triangle. This is similar to (2aa){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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring