Dynamic Programming: Count the no of hops required to reach the destination

Write a program to find the no of hops requried to reach the end using dynamic programming approach

Java Code

import java.util.*;

 class ChildHopDP{
    
        HashMap<Integer, Integer> hash = new HashMap<>();
        int[][] stored = new int[3][3];
    
        public int childHop(int n){
            System.out.print(".");
            if(n < 0) { return 0; }
    
            if(n == 0) { return 1; }
    
            return childHop(n-1) + childHop(n-2) + childHop(n-3);
        }
    
        // using dp
        public int childHopMemo(int n){
            System.out.print(".");
            if(n < 0) { return 0; }
    
            if(n == 0) { return 1; }
            
            if(hash.get(n) == null){
                int x = childHopMemo(n-1) + childHopMemo(n-2) + childHopMemo(n-3);
                hash.put(n,x);
            }
    
            return hash.get(n);
        }
    
        public static void main(String args[]){
    
            int nn = 7;
            ChildHopDP dp = new ChildHopDP();
            System.out.println("The child can use 1, 2 or 3 hops and reach the destination in 
                  "+dp.childHop(nn) + " ways.");
            System.out.println("The child can use 1, 2 or 3 hops and reach the destination in 
                  "+dp.childHopMemo(nn) + " ways.");
        }
  }

Output

.............................................................................................................................................................The child can use 1, 2 or 3 hops and reach the destination in 44 ways.
......................The child can use 1, 2 or 3 hops and reach the destination in 44 ways.
 

Note

In the above output the dot indicates the no of times the childHop() function was called by program.
You can clearly see that in the dp approach, we called the function childHopMemo() less no of times as compared to normal recursion approach.
DP approach allows us to save intermediate function call computations and reuse it, so its fast.