A **lattice path** is composed of horizontal and vertical lines that pass through #key# lattice points: Points at the intersection of two or more gridlines in a regularly spaced array of boxes. #key#. 

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


# 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;
}

//function to calculate paths
function paths(n){
    // apply the above stated rule for n iterations
    var j = 1
    for (var i = 1; i <= n; i++)
    {
        j = j * (n + i) / i;
    }
    return j;
}
// enter grid size
p = paths(0)
//print paths
console.log(p);

JavaScript


#function to calculate paths
def paths(n):
#apply the above stated rule for n iterations
    j = 1
    for i in range(1,n):
        j = j * (n + i) / i
    return j

def main():
  # input grid size
  p = paths(0);

#print paths
  print('The number of paths are:')
  print p

main()

Python

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. 