Doubt in tilling problem

#1

can you help me with the code please

#2

hi @adarshsingh2k i see you passed all the test cases, what do you need help with?

#3

i used dp to sole it can you help me with the code for recurssion

#4

@adarshsingh2k have you copied this code from somewhere?

#5

yeah i took refernce from other platforms

#6

@adarshsingh2k dont copy the code blindly. The code that you submitted is using recursion with memoization, ie top-down DP.

#7

can you just tell me simple approach and base case

#8

for 2*3 we have two ways i.e. either horizontally or vertically

#9

@adarshsingh2k
does this mean you did not even read the code you submitted?

The recurrance relation is:
f(n) = f(n-1) + f(n-m);

Read the code once and see the base conditions used there.

#10

hey i read code and editorial both the reason i asked bcoz i am not able to get the base condition from code

#11

@adarshsingh2k
image

These are the base conditions:

if (n < 1) return 0;
if (n == m) return 2;
if (n < m) return 1;

Recursive case:

return f(n-1, m) + f(n-m, m);
#12

@adarshsingh2k the code will give TLE without memoization, this is why it must be used.

#13

what is memoization can you tell please

#14

@adarshsingh2k it is a technique used to remember the answers that have already been calculated to avoid calculating the same thing again and again. I would recommend you to watch the initial lectures on DP to get a better idea.

#15

is there any other way to solve it

#16

@adarshsingh2k no it can be solved by DP only

#17

is it explained in dp section

#18

hi @adarshsingh2k memoization (top-down DP) is explained in the DP section.

#19

i am asking about tilling problem

#20

hey did you delete my messages