I was reading a article on the CP-ALGORITHM and I encounter with given question and after reading the solution of what they have given, I was not able to find out how it should be done, I also have searched for similar problems or content but not fortunate to find out.. Will anyone please help me to get to know about this, how it will be done.. Here is the link to the article.. Link

We often need to find total number of path from one point to another in a N*M grid. There are different solution for this,like naive approach or using formula but we can not use formula every time... So here we discuss the Dynamic Programming approach to solve the problem...

Let's say we have a grid of Matrix of size N*M..

         ______________________
         |   |    |   |   |   |
         |___|____|___|___|___|
         |   |     |   |  |   |   
         |___|____|___|___|___|
         |   |     |   |   |   |
         |___|____|___|___|___|

Now we start form the upper left Corner and first we traverse only on the first row and put 1 in there as we know there is only one path from (1,1) to any point in the first Row...

Similarly we traverse on the second column and put 1 in there as there is only one path from (1,1) to any point in the first column..

Now the fun begins:)

Let's say we are in the secind row and second column. Ni=ow if we see there are two possible way to come at 
    this place,
either from the top or from the left to the current block i.e. at (2,2) = (1,2) and (2,1)...  we can reach 
    (2,2) from (1,2) and (2,1)...
So the total number of path to (2,2) is the sum of total number of path to (1,2) and total number of path 
    to (2,1)...

So dp[2][2] = dp[2][1] + dp[1][2]

So total number of ways to reach a point (i,j) is given by the formula...

          **dp[i][j] = dp[i][j-1] + dp[i-1][j]**
                    ====================================



                So at last our dp table will look like this...

         ___________________________
         |    |     |    |    |    |
         |__1_|__1__|__1_|__1_|_1__|
         |    |      |  |    |     |     
         |_1__|__2__|_3_ |__4_|_5__|
         |    |      |  |    |     |     
         |__1_|__3__|_6__|_10_|_15_|

So to reach to (3,5) from (1,1),there are total 15 ways to reach  that point...
It is highly recommend to run the given program and use pen and paper to see how it is working... So in 
    that at way you will never forgot to implement in the programming contest...

#include <bits/stdc++.h>
	using namespace std;

	int main()
	{
		int n,m;
		cin>>n>>m;                     // size of the grid

		int dp[n+1][m+1];               // I will consider indexing from 1 

		for(int i=1;i<=m;i++)
			dp[1][i] = 1;              // we will set 1 in the first row as discussed earlier..

		for(int i=1;i<=n;i++)
			dp[i][1] = 1;              // We will set 1 in the first column as discussed

		for(int i=2;i<=n;i++)
		{
			for(int j=2;j<=m;j++)
			{
				dp[i][j] = dp[i][j-1] + dp[i-1][j];
			}
		}


	}

The time complexity of these approach is O(N*M) which is far better than the naive approach...
The space complexity is O(N*M)...

So that's all from my side... If you have any query just write it down in comments...I will be more than happy to answer your Questions...

We often get confused which data structure or Algorithm we should use while in competition and sometimes if we doesn't use good Data Structure while in competition, it may lead to not able to solve a simple question easily..

So here is my blog which will help you to Use agood Data Structure during a contest...

1. Set..

2. We use Set when we want to deal with only unique elements..

3. If we try to Insert a value already present in a Set it will automatically discard it..

4. Insertion, Deletion, Searching in Set take place in log(n) time...

5. In Set, Elements are arranged in Sorted Order....

5.If You only want Unique element in Set then you can use Unordered_Set in place of Set...Just replace set with unordered_set....

:- To insert a element in Set...

: #include<bits/stdc++.h> using namespace std;

    int main()
    {
       set<int>S;
       S.insert(5);
    }

<------------------------------------------------------------------------------------>

:- To delete a element in Set..


    #include<bits/stdc++.h>
    using namespace std;

    int main()
    {
       set<int>S;
       S.erase(5);
    }

<------------------------------------------------------------------------------------>

:- To Search an element in array..


    if(S.find(Element_To _Searhc)!=S.end())
    {
       //Element Found
    }
    else
    {
       //Element Not Found..
    }

<------------------------------------------------------------------------------------> :-To iterate in Set...

#include<bits/stdc++.h>
    using namespace std;

    int main()
    {
       set<int>S;
       for (auto x:S)
         cout<<x<<" ";
    }

<################################################################################################################>

2.Priority Queue =

1. We use priority_queue when we want largest or smallest element  from the given set of  elements in 
       constant time...

2.It uses Concept of Min-Heap and Max-Heap...

3.Insertion and Deletion take place in logn time..

4.When you want to get largest or smallest element frequently you should use priority_queue()..


:- To insert element in priority_queue()

    int main()
    {
       priority_queue<int>p;

       for(int x:{2,45,12,3,1})
         p.push(x);


    }

<------------------------------------------------------------------------------------>

:- To delete element in priority_queue()

    p.pop();

<------------------------------------------------------------------------------------>

:-To traverse in priority_queue()

    int main()
    {
       priority_queue<int>p;

       for(int x:{2,45,12,3,1})
         p.push(x);


       while(!p.empty())
       {
         cout<<p.top()<<" ";
         p.pop();
       }


    }

<################################################################################################################>

1. Map

1. We use Map when we want to form a key value pair..

2. It is same as Dictionary in python...



    int main()
    {

       map<int, int>m;

       m.insert({2,4});       //First Way

       m[3] = 45;                              // Second Way
    }

<#####################################################################################>

1. Binary Search.

You should always use Binary search when you want to perform Searching operation on an array or vector..

Note : You can only use Binary search only when You have Elements in sorted order...



bool Binary_Search(int arr[], int n, int key)
{
    int low = 0;
    int high = n;

    while(low<=high)
    {
       int mid = (low+high)/2;

       if(arr[mid]==key)
         return true;

       else if(arr[mid] > key)
         high = mid-1;
       else
         low = mid+1;
    }
    return false;
}

int main()
{
    int arr[] = {1,23,45,67,68,80};

    int n = sizeof(arr)/sizeof(arr[0]);

    if(Binary_Search(arr,n, 1))
    {
       cout<<"Element Present\n";
    }
    else
       cout<<"Element Not Present\n";
}

<################################################################################################################>

Thank You for Reading Post......