Tilling problem-2 related doubt

#1

Initially I solved it without using any DP, I got TLE. But, I finally solved it without getting TLE by using Bottom-Up DP approach. But, when I approached the problem using Top-Down DP , I got “wrong answer”(NOT TLE). Although Top Down DP was also giving right answers when I manually entered large sample inputs. But still the result was “Wrong answer” when submitted in this IDE. I would have left this thing there and forgot had I got “TLE”, but I don’t understand why my Top-Down is giving “wrong answer”. P.S: I have solved it without any issue by using Bottom-Up DP, but just wanted to know what’s wrong with my Top-Down DP and why its giving “Wrong Answer”(not TLE). Here is my code(Includes both the approaches I used)- https://ide.codingblocks.com/s/227719

#2

@a_krisna22 There are two changes that you need to do in your dp code, 1st one is if(n<=0)return 0
because if you do dp[n]=0 then the index can be negative.

Also initialize your dp your with 0 for every test case, because your dp array is global but there will be cases for other test cases when ‘n’ is same as previous but with different ‘m’.
Rest all is correct.

#3

Feel free to ask if any doubt remains.
Otherwise please mark this doubt as resolved if you got it.