Dynamic Programming: Count the no of possible paths in a matrix

Write a program to count the no of possible paths in a matrix using dynamic programming approach

Approach

• In this program we count the number of possible paths in a matrix
• We display two approaches: using normal recursion and using dynamic programming
• To demonstrate how fast dp is, we are printing a '.' every time the method is called to count the path
• An important fact about dp: you always store the computed value of a subset and use it afterwards
• This approach of storing the intermediate computation results is called memoization

Java Code

import java.util.*;

 class CountPathDP{
    
        HashMap<Integer, Integer> hash = new HashMap<>();
        static int[][] stored = new int[4][4];
    
        public int countPathNormal(int[][] a, int row, int col){
            System.out.print(".");
            if(row > a.length-1 || col > a.length-1){ return 0 ;}
    
            if(row == a.length-1 && col == a.length-1){
                return 1;
            }
            
            return countPathNormal(a, row+1, col) + countPathNormal(a, row, col+1); // the last 
                                                                                    // cell
        }
    
        public static int countPathUsingDP(int[][] a, int row, int col){
            System.out.print(".");
            if(row == a.length-1 || col == a.length-1){ return 1;}
            
            if(stored[row][col] == 0){
               stored[row][col] = countPathUsingDP(a, row+1, col) + countPathUsingDP(a, row, 
                 col+1);
            }
    
            return stored[row][col];
        }
    
        public static void main(String args[]){
    
            int nn = 15;
            int[] map = new int[5000];
            
            for(int i = 0; i < map.length; i++){
                map[i] = -1;
            }
    
            CountPathDP dp = new CountPathDP();
            int[][] ab = new int[4][4];
    
            ab[2][1] = -1;
            ab[2][2] = -1;
    
            System.out.println("Using normal recursion: " + dp.countPathNormal(ab,0,0));
            System.out.println();
            System.out.println("Using dp method: " + dp.countPathUsingDP(ab,0,0));
        }
 }

Output

...................................................................................................Using normal recursion: 20
...................Using dp method: 20

Please note the output displays the no of times the program called the function to get to the final result.
Its evident that using DP approach, we are able to calculate the result in less time and making fewer calls to the method.