• Techiax

Dynamic Programming - Find number of ways to reach the destination







Today we are going to give you some knowledge on dynamic programming and we are going to solve a good example of dynamic programming. First, let us get into the problem.





Problem:


You are given series of square grids like the image. Your goal is to find the number of ways we could reach the destination. And the constraint is that you could move only to the right grid and grid below. The start is marked with green and end is marked with red.

Also Read: Tutorial - C programming - Decision Statements 


Solution:


First, you might be thinking of using a recursive algorithm to solve this problem. The recursive algorithm might produce the result but has very high time complexity i.e takes more time to execute. And you need to repeat the process for each repetition. It is not the best solution to this problem.

We could solve this problem easily with a little work of dynamic programming(DP) algorithm. Dynamic programming use memorization or caching to store previous results which may be used to get the required result. Let's see it in detail.





If you see the problem closely you could see a good relationship between grid. Look at the images below, you could see that the only way to reach the red boxes is to go through the pink boxes.









Also Read: Solve your mathematical problems by just taking photo of your problem



Look at this image. There are 6 ways to reach red box.



Now look at the same destination with pink boxes. Each pink box can be reached by 3 ways. As you know that the destination can be reached only through pink boxes, you just add the values of two pink boxes which will give the value of the destination.

3 + 3 = 6



Have your got the solution from the tips above.
Yeah, that's it. Add the values to reach the top and left boxes to get the value of the destination box.

Also Read: Tutorial - Structures for C++


That's it. Now you can find the ways for each box with the same concept.
To do it, start with the first box and iterate over all the boxes in the row-wise order and find the value of each box at the iteration.

Now let's see the programming solution to solve this problem. I am using C to solve, you could any language to solve this.



    #include<stdio.h>
    int main(){

        int grid[5][5];  //Defining an 5x5 grid
        int i,j;

        //put values for first row and column as 1
        for(i=0;i<5;i++){
            grid[0][i]=1;
            grid[i][0]=1;
        }

        //iterate over the grid to find the value of each box
        for(i=1;i<5;i++){
            for(j=1;j<5;j++){
                //Add top and left box value to get current box value
                grid[i][j]=grid[i-1][j]+grid[i][j-1];
            }
        }

        //to Find the ways to reach a box, just print the grid value
        printf("\nThe ways to reach box at grid 2x2 is %d",grid[1][1]);
        printf("\nThe ways to reach box at grid 3x3 is %d",grid[2][2]);

        //Now use your talent to modify the program to your needs.
        //Happy Programming

      }



If you have any queries, please let us know in comments below.

Please share your views and thoughts that would make us do  more for you.

Also Read: Tutorial - C programming - Decision Statements







Author:

I am an enthusiastic person striving to gather as much information as possible to achieve higher heights and to share the information to all others to make them also reach the stars.
"People who are crazy enough to think they can change the world are the ones who do"
-Steve Jobs.

Previous Post
Next Post
18 September 2017 at 03:43

Pretty helpful for the programmers and moreover for the students using the technique in the projects. It really is helpful in programming the robots for maze solving.

Reply
avatar