Number of paths in a matrix with k coins.txt

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     
	 public static void main (String[] args) throws IOException
	 {
	 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	 StringBuffer sb=new StringBuffer();
	 int T=Integer.parseInt(br.readLine());
	 while(T-->0)
	 {
	     int k=Integer.parseInt(br.readLine());
	     int n=Integer.parseInt(br.readLine());
	     int count=0;
	     String[] s=br.readLine().split("\\s");
	     int[][] arr=new int[n][n];
	     for(int i=0;i<n;i++)
	     {
	         for(int j=0;j<n;j++)
	         {
	             arr[i][j]=Integer.parseInt(s[count++]);
	         }
	     }
	     long[][][] dp=new long[k][n+1][n+1];
	     for(int i=0;i<k;i++)
	     {
	         for(int j=0;j<n+1;j++)
	         {
	             for(int l=0;l<n+1;l++)
	             {
	                 dp[i][j][l]=-1;
	             }
	         }
	     }
	     long ans=solve(arr,n,k-arr[0][0],0,0,dp);
	     sb.append(ans+"\n");
	 }
	 System.out.print(sb);
	 }
	 public static long solve(int[][] arr,int n,int k,int i,int j,long[][][] dp)
	 {
	     if(k<0)
	     {
	         return 0;
	     }
	     if(i==n-1 && j==n-1 && k==0)
	     {
	         
	         return 1;
	     }
	     if(dp[k][i][j]!=-1)
	     {
	         return dp[k][i][j];
	     }
	     long smallans1=0,smallans2=0;
	     if(canplace(i+1,j,n))
	     {
	         if(k-arr[i+1][j]>=0)
	         {
	             smallans1=solve(arr,n,k-arr[i+1][j],i+1,j,dp);
	         }
	     }
	     if(canplace(i,j+1,n))
	     {
	         if(k-arr[i][j+1]>=0)
	         {
	             smallans2=solve(arr,n,k-arr[i][j+1],i,j+1,dp);
	         }
	     }
	     dp[k][i][j]=smallans1+smallans2;
	     return dp[k][i][j];
	 }
	 public static boolean canplace(int i,int j,int n)
	 {
	     return i>=0 && j>=0 && i<n && j<n;
	 }
}