Recursion challenge : tiling problem

#1

import java.util.*;

public class Main{
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();

        if(n<m)   //only horizontal placement
        {
            System.out.println("1");
            continue;
        }

        if(n==m)     //place everything either horizontally or 
                       vertically
        {
            System.out.println("2");
            continue;
        }


        System.out.println(countWays(0,n,m));
    }
}

static int countWays(int row, int n, int m)
{   
    if(row == n)
    {
        return 1;
    }

    if(row > n)
    {
        return 0;
    }
    
    int cnt = 0;

    cnt += countWays(row+1, n, m);  //for placing 1 tile horizontally
    cnt += countWays(row + m, n, m); //for placing tiles vertically

    return (cnt % (1000000007));
}

}

This code results into TLE for n>>m. Could you suggest some changes in this recursive code?

#2

Tile placed horizontally(one row is covered now recurse for remaining rows):-
countWays(n - 1, m)

Tile placed vertically if and only if :-
if(n - m >= 0) {
countWays(n - m, m)
}
Now where is the issue, try to visualize the case for 4*3.
there is a 4 * 3 floor, then you have a 1 * 3 tile.

  • Now if you place the tile horizontally then you have 3 * 3 floor left to tile.
    So you make a call for say tiling(n - 1) i.e n - 1 rows left to tile.
  • Now one vertical call is made by you in the code. So your work is to add the horizontal call.
#3

You are not using dp. Then you will get TLE

#4

public static long TillProblemBU(int n, int m) {

	long dp[] = new long[n + 1];
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1]%mod;
		if (i - m >= 0) {
			dp[i] = (dp[i] + dp[i - m]%mod)%mod;
		}
	}
	return dp[n]%mod;
}