lattice paths

class Result {
​
    /*
     * Complete the 'latticePaths' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER m
     *  2. INTEGER n
     */

    private static int destM, destN;
    private static HashMap<String, Integer> cache;
​
    public static int latticePaths(int m, int n) {
        //Top-down Approach with Pure Recursion
//         //Base Cases
//         //1. Origin reached
//         if(m==0 && n==0) return 1;

//         //2. Out of bounds
//         if(m==-1 || n==-1) return 0;

//         //Make recursive Calls
//         int recurseUp = latticePaths(m-1, n);
//         int recurseLeft = latticePaths(m, n-1);

//         //Return result
//         return recurseUp + recurseLeft;

        //Bottom-up Approach with Helper Method Recursion with Memoized Cache
        // destM = m;
        // destN = n;
        // cache = new HashMap<>();
        // return helper(0,0);

        //Iterative Tabulation Approach
        int[][] T = new int[m+1][n+1];

        T[0][0] = 1;
        //Fill out top row of table
        for(int row=1; row<=m; row++) {
            T[row][0] = T[row-1][0];
        }

        //Fill out left col of table
        for(int col=1; col<=n; col++) {
            T[0][col] = T[0][col-1];
        }

        //Fill out rest of table
        for(int row=1; row<=m; row++) {
            for(int col=1; col<=n; col++){
                T[row][col] = T[row-1][col] + T[row][col-1];
            }
        }
        return T[m][n];

    }


    private static int helper(int m, int n) {
        //Base Cases
        //0. Check cache
        String key = Integer.toString(m)+"_"+Integer.toString(n);
        if(cache.containsKey(key)) return cache.get(key);

        //1. Destination reached
        if(m==destM && n==destN) return 1;

        //2. Out of Bounds
        if(m >destM || n >destN) return 0;

        //Recurse down rows or right columns
        int count = helper(m+1, n) + helper(m, n+1);
        cache.put(key, count);

        return count;
    }
​