Problem - F - LCS
My solution - Submission #15892946 - Educational DP Contest
I tried to run the code on my machine with large input.
It runs pretty fast [998 length string took 29 ms].
Can somebody help me understand what am I missing?
1 Like
Try initializing the dp array to -1 instead of 0.
It can be the case that the LCS is actually zero and in that case, the recursion won’t end until it hits the base case (0,0). You can terminate early in these cases, which is missed by your code.