I think that you should initialize dp with zeroes and then take care of this:

else cur[j]=0;

If the last two elements are different, it doesn't mean that the length of the LCS is 0.

I'm not sure if I understood your code right. Why don't you just take the reversed string and use 2D DP or just DP[from][to] without computing the LCS:

Let dp[i][j] gives us the answer for the sequence S[i],S[i+1],...,S[j].

Then you have two cases:

If S[i]==S[j], then dp[i][j]=dp[i+1][j-1].

If S[i]!=S[j], then dp[i][j]=1+min(dp[i+1][j],dp[i][j-1]).

I just got accepted.

My first idea was the one that I shared with you yesterday — dp[from][to] but it received TLE:

ioipalin1

My second idea was actually the same but my dp looks like dp[i][from], not dp[from][to] because this can be easily space optimized. However, this second idea got AC(I don't know why):

ioipalin2

But I made an optimization and it got AC with linear space:

ioipalin3

You asked me how to optimize (from,to) with PM. I am using my phone now and I can't write a PM. Those who have tried will know. So my answer goes here:

Actually I don't even know if it is possible to optimize it and that is why I transformed dp[from][to] to dp[length][from] where length=to-from. Then to calculate the state (length,from) we need only the states with length-1 and length-2. Check my second and third posted codes to understand it completely.

Optimise space. You can see that in LCS :

dp[i][j] = max(dp[i-1][j],dp[i][j-1]) for non equal a[i] and b[j]

dp[i][j] = dp[i-1][j-1] for equal a[i] and b[j]

Now you can observe that for a state(i,j) you need information of only two rows, i and i-1. This can help you reduce your state drastically. Create an array of 2 * N instead of N * N.