Tiling Problem - Wrong answers

#1

Test Cases are failing. Please explain the question in detail as well. What I have understood is that we can place a tile either horizontally or vertically. But my code isn’t getting submitted. Please go through it.

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();

	    int cnt=tiling (n,m);
	    System.out.println (cnt);
	}

}

static int tiling (int n, int m) {
	if (n==0) {
		return 1;
	} else if (n<0) {
		return 0;
	} else {
		return tiling (n-1,m) + tiling (n-m,m);
	}
}

}

#2

Imagine you have a floor of size n × m and you are given tiles of size 1× m.
Now you can either place the tiles vertically. Where a tile can be either place vertically,meaning it will only occupy a cell of width 1 and a complete height of M

there are 3 possibilities:

n>m - here you can place a tile vertically(left with n-m,m) as well as horizontally(left with n-1,m).
n==m then there are always 2 ways - horizontally or vertically.
n<m here you have only 1 choice,that is to place tile horizontally, so 1 way only.
Also mere recursion won’t help in passing all test cases, dynamic programming
image

another example:
image

#3

See this

#4

Thank you for the explanation. My code has got submitted now :slight_smile: