Tried with recursion as well memoiztion still not working

#1


can you tell me y memo dp also doesnt work?
also any modifications required?

#2

hi @Krishna-Singh-2678805765519156 the logic is correct but you need a bigger dp array according to the constraints of the problem. 1 <= N,M <= 100000
Also if you notice, the value of m is not changing at all, so you needn’t maintain a dimension for that. Just maintain a 1D dp array to store values according to n.
In short, this relation
f(n,m) = f(n-1, m) + f(n-m, m)
can also be written like this
f(n) = f(n-1) + f(n-m)

#3


still shows wa on many cases

#4

@Krishna-Singh-2678805765519156 try by using long long int for all the variables

#5

@Krishna-Singh-2678805765519156 you missed a base case, when n==m return 2, n < 0 return 0, n >0 && n < m return 1

#6

n==m test case is being take cared of! also n<0 wont occur as if n<m i am returning 1.
Maybe do you think this is a problem of stackoverflow? but in such case it should show mle and not wa.

#7

also as the range is 10^5 it can be covered by int only. But long long also doesnt help

#8

i am setting memset everytime for t testcase is that okay?

#9

@Krishna-Singh-2678805765519156 memset has to be done everytime because answer will vary according to different value of m, so dp array must be reset. Range of n is 10^5 but range of the answer may exceed.

#10

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.