I tried Dynamic programming approach and i still get RE for the code for tiling problem -2

#1

Please help me find the error

def tile(n, m, s):
if n==m:
return 2
elif n<m:
return 1
if s[n]!=-1:
return s[n]
a = tile(n-1,m,s)
b = tile(n-m,m,s)
s[n] = a+b
return a+b

t = int(input())
for _ in range(t):
n, m = list(map(int, input().split()))
s = [-1] * (n+1)
if m > n:
print(1)
continue
elif m == n:
print(2)
continue
for i in range(m):
s[i] = 1
s[m] = 2
x = tile(n, m, s)
print(x)

#2

@gandikotasasia1_d6d586dbd5c4388c please share your code using ide.codingblocks.com

#3

should i share that through email?

#4

@gandikotasasia1_d6d586dbd5c4388c no just save your code on ide and share the link here

#5


Done

#6

@gandikotasasia1_d6d586dbd5c4388c

if m > n:
        print(1)
        continue
    elif m == n:
        print(2)
        continue

These base cases should be inside the recursive function as well

#7

Yes, I have included them inside recursion also

#8

@gandikotasasia1_d6d586dbd5c4388c

  1. Print answer for every test case in a new line modulo 10^9+7.

  2. Sample test case

10
39462 25602 
29680 52811 
83054 93356 
29602 66791 
14717 78403 
55774 64800 
67309 8625 
29315 41141 
7428 17804 
86402 1354
#9

It says maximum recursion depth exceeded
But I have used DP approach so that should solve it?

#10

@gandikotasasia1_d6d586dbd5c4388c must be a python issue, my c++ code with the same logic passed all cases https://ide.codingblocks.com/s/584809

#11

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.