How to reduce to time complexity of this code

#1

import java.util.*;
public class Main {
static long answer(int n,int m,HashMap<Integer,Long> map)
{
if(n==0)
return 1;
if(n<0)
return 0;

      if(map.containsKey(n)) 
    	  return map.get(n);
      

          long way1=answer(n-1,m,map);
          long way2=answer(n-m,m,map);
          map.put(null, way1+way2);
        return (way1+way2);
    } 
public static void main(String[] args) {
	Scanner sc =new Scanner(System.in);
	int t=sc.nextInt();
	while(t!=0) {
  int n=sc.nextInt();
int m=sc.nextInt();
	HashMap<Integer,Long> map=new HashMap<>();
	System.out.println(answer(n,m,map));
 t--;	}

}

}

#2

@sksumitkumardiwaker

  • A tile can be either place vertically,meaning it will only occupy a cell of width 1 and a complete hieght of M. Or,
  • You can place M tiles horizontally one over the other if there is enough width left.
    try to solve this problem using dynamic programming think how you can broke this problem into sub problem and then using them to solve bigger problem
#3

Can you send me pseudo code

#4

@sksumitkumardiwaker

for(ll i=1;i<=n;i++){
      // Placing the tile vertically
      dp[i]=dp[i-1];
      // Placint the tile horizontally if there is space
      dp[i]+=((i-m)>=0)?dp[i-m]:0; 
    }