DP Problem TLE Atcoder Educational DP Contest

Problem - https://atcoder.jp/contests/dp/tasks/dp_f
My solution - https://atcoder.jp/contests/dp/submissions/15892946

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.