Lattice Paths Problem

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?

Solution:

void Solution()
        {
            //Lattice Path Problem
            //The number of possible path at (i,j) = BinCoff(i+j,j)
            // So for 20x20 matrix it will be
            long x = BinomialCoefficient(40, 20);
        }

        static long BinomialCoefficient(long n, long k)
        {
            // return fact(n) / (fact(k) * fact(n - k));

            long divFactor = k > (n - k) ? k : (n - k);
            long restProd = 1;
            bool flag = true;
            long counter = 1;
            if (divFactor == k)
            {
                for (long i = 0; i < (n - k); i++)
                {
                    restProd = restProd * (k + 1 + i);
                    if (restProd % counter == 0 && flag)
                    {
                        restProd = restProd / counter;
                        //flag = false;
                        counter++;
                    }
                }
                return restProd;// / fact(n - k - counter);
            }
            else
            {
                for (long i = 0; i < k; i++)
                {
                    restProd = restProd * ((n - k) + 1 + i);
                }
                return restProd / fact(k);
            }


        }

        static long fact(long i)
        {
            if (i == 0)
                return 1;
            else
                return i * fact(i - 1);
        }

No comments :

Post a Comment

Comment Here