Trusted answers to developer questions

Educative Answers Team

A **lattice path** is composed of horizontal and vertical lines that pass through

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}$.

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

Copyright Ā©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses