Instead of DP, I use direct recursive method. 31/33 tests have been passed, but I cannot pass the 32rd test. The list is too long to test in my own laptop and I do not know what I can do.
Can anyone tell me why my codes cannot pass it? Is there any trick here?
Thank you in advance.
Judging from 'instead of DP', I assume you did not use any form of memoization in the 'recursive method'. If so, then of course your code would spend too much time on the long test cases (specifically 32 and 33). For this problem, the 'trick' is to use DP; there is not a better way.
PS: Next time you ask 'why my code cannot pass it'. You have to show us what 'your code' is with the exact error message (TLE? MLE? WA?), rather than just saying 'cannot pass'.
DP will remember answers to the intermediate steps that you can conveniently refer to in later steps, while recursing will calculate those steps over and over again when they are needed, instead of saving them for sharing. So you see, recursing will take a lot more time.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.