Tiling problem TLE

#1

Getting TLE, what’s wrong?

#2

hello @rockstarpkm

a) recursive solution for this problem has exponential time complexity thats why it is showing tle.
use dynamic programming
b) also your recurrence relation is not correct.
it should be
T(n,m)=T(n-1,m) ( when placed vertically) + T(n-m,m) (when placed horizonatlly).

#3

can you explain the recurrence relation

#4

let say we have M X N box.

if we place a tile vertically(i.e MX1) then dimension of box will reduce to M X (N-1).

if we place tile horizontally i.e (1XM) then we need to put M such tile to cover M rows
and dimension will reduce to M*(N-M).

so if we need to calcuate number of ways. then we can says
ways(m,n)=ways(m,n-1) + ways(m,n-m)

#5

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.