// Count Grid Unique Paths-->2-D dp concept(Memoization)

// tc = O(mxn) -->at max there will be n*m calls of recursion

// sc = O((n-1)+(m-1)) + O(mxn) --> stack space + extra dp array

import java.util.*;

class dp {

     public static int f(int i , int j, int dp[][])

     {

        if(i==0&&j==0) return 1;

        if(i<0||j<0) return 0;

        if(dp[i][j]!=-1) return dp[i][j];

        int up = f(i-1,j,dp);

        int left = f(i,j-1,dp);

        return dp[i][j]=up+left;

     }

    public static void main(String args[]) {

        int m = 3;

        int n = 2;

        int dp[][] = new int[m][n];

        // Initialize the DP array with -1 to indicate uncomputed values

        for (int[] row : dp)

            Arrays.fill(row, -1);

        System.out.println(f(m-1,n-1,dp));

    }

}