Total Ways to traverse a n*m board using Dynamic Programming in Java

In this Java tutorial, we are going to find the total number of ways to traverse a board consisting of n*m blocks using Dynamic Programming approach. Finding the total number of ways to traverse a n*m board in Java is very easy with Dynamic programming.

Why Dynamic Programming?

The given problem can also be solved using recursive function calling approach but here we are using Dynamic approach because the problem has overlapping subproblems and in calculating the same subproblem again and again increases the time complexity to exponential.

Dynamic Programming approach stores the value of subproblems and instead of calculating it again when needed it uses stores values which leads to time complexity in linear.

Also, learn

• Maximum Coin Spend Problem using Dynamic Programming in Java
• Total ways to reach the destination by snake using Backtracking In Java

The general approach for the Problem

A number of ways to reach a block in board = No. of ways to reach the piece above it + No. of ways to reach the block left to it in board. So, after filling the 2-D array the last element of the array will be our answer.

Step by Step Approach for total no. of ways to traverse n*m board

1. Input value of n and m .
2. Build a (n+1)*(m+1) table and fill up it bottom-up manner.
3. If there is a single row or single column, then return no. of ways as 1, otherwise, return value of each block as the sum of the block above it and block left to it.
4. Return the value of the last block which is our answer.

Java code to find total no. of ways to reach the bottom-right corner of the board from top-left block

import java.util.Scanner;

class Codespeedy
{
    static int result(int a , int b)
    {
       int dp[][] = new int[a+1][b+1];
       
       for(int i=1;i<=a;i++)
        {
            for(int j=1;j<=b;j++)
             {
                 if(i==1 || j==1)
                    dp[i][j]=1;
                    
                else
                  dp[i][j]=dp[i-1][j]+dp[i][j-1];
             }
        }
        
        return dp[a][b];
    }

  public static void main(String args[])
  {
      int n,m ;
      
      Scanner scan = new Scanner(System.in);
      
       n=scan.nextInt();
       m=scan.nextInt();
       
         System.out.println(result(n,m));
  }
}

INPUT

5

5

OUTPUT

70

You can also learn,

• Total ways to reach destination by snake using Backtracking In Java