Problem IN approach

#1

i am unable to figure out the base case :
the recursive case i thought of was :
return fun(n-1,m) + fun(n,m-1);

please help

#2

hi @tusharbhardwaj127 the correct recursive case is:
f(n, m) = f(n-1, m) + f(n-m, m);

m will not change, the height is constant, but the width will decrease as we add more tiles

#3

so what would be the base case ?

#4

hi @tusharbhardwaj127
the base cases will be:
if n<=0, ans = 0
if n==m then we can have two configurations, all the tiles vertically or all the tiles horizantally, so ans = 2
if n>0 && n<m then we can have only 1 configuration(try to draw it on your own) so ans = 1

for n>m cases(remaining cases), we call the recursive function.

#5

i tried implementing it, but its giving TLE for 4 test cases. One more issue regarding the case when we make a recursive call f(n-m,m)…here when place a tile of M x 1 wouldn’t the width of the untiled floor decrease by 1 ? https://ide.codingblocks.com/s/308690

#6

hi @tusharbhardwaj127 the time complexity of recursion is very high by itself, so you’ll have to use memoization to reduce the time complexity. It is covered in the DP section, also known as the top-down approach.

#7

@tusharbhardwaj127

floor is of dimension nxm
see we have 2 options, either we can place 1, 1 x m tile(vertically), then out subproblem becomes f(n-1, m) or we can place m tiles of the dimension m x 1(horizontally), then our subproblem becomes f(n-m, m)
We add the answer for both the cases.