Tilling Problem

#1

import java.util.*;

public class Main
{
public static int countWays(int n,int m){

    if(n<=0 || m<=0){
        return 0;
    }
    
    if(n == m){
        return 2;
    }
    
    if(n < m){
        return 1;
    }
    
    int count = countWays(n-1,m);
    if(n>m){
        
        count =  count + countWays(n-m,m-1);
       
    }
    
    return count;
    
}

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();
        System.out.println(countWays(n,m));
        
        
    }
}

}

My code is working only for 1 test case…

#2

@Mukul70
recursion will give TLE in this question you have to optimize your code.

Read the problem as a matrix of size M x N, rather than N x M as it helps in easy visualization.
In this manner,

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.

#3

But this is a recursion problem in my course…

#4

Can we solve it using recursion?

#5

@Mukul70
you have to use dynamic programming here then only it will get submit.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#7

Hello brother, How can I share my code on this platform