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 pathsint paths(int n){// apply the above stated rule for n iterationsint j = 1;for (int i= 1; i <= n; i++){j = j * (n + i) / i;}return j;}int main() {// input grid sizeint p = paths(0);//print pathscout << "The number of paths are: "<< p << endl;return 0;}

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS