Problem15 Lattice Path

 
        

                                              Lattice paths

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Recursive solution that works till 16x16 grids

#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <stdio.h>

long long int n=20;
long long int countPath(long long int i,long long int j)
{
    if(i > n || j > n)
        return 0;

    if(i == n && j==n)
    {  
        return 1;
    }  

  
   return countPath(i+1,j) + countPath(i,j+1);
//count[i][j]=countPath[i+1][j] + countPath[i][j+1]
}

int main()
{
    printf("%llu\n",countPath(0,0));

}

Converting the recursive function into DP based solution


#include <stdio.h>
#define B 20
#define n (B+1)
unsigned long long int DP[n+1][n+1];
unsigned long long int PathCount(unsigned long long int i,unsigned long long int j)
{
  for(i=0; i<n; i++)
      DP[i][0] = 0;

  for(j=0; j<n; j++)
      DP[0][j] = 0;


    for(i=1; i<=n; i++)
    {  for(j=1; j<=n; j++)
      {
          if(i==1 && j==1)
              DP[1][1] = 1;
          else
              DP[i][j] = DP[i-1][j] + DP[i][j-1];

      }
    }


  return DP[n][n];
}
int main()
{
    printf("%llu\n",PathCount(n,n));

}

Answer:-

137846528820