Блог пользователя Amidrunk

Any help will appreciated !
Автор Amidrunk, 13 лет назад, По-английски

I was solving this Problem , which is basically a LCS problem, where we have to find the length of LCS between given string and its reverse to compute the solution for it.

Problem what I am facing:

I am able to write an O(n^2) algorithm for it, but it is a TLE for the given constraint for the above mentioned problem. I dont know how to optimise it, before posting here, I tried searching an efficient implementation/algo for LCS , and I got this and this. But I am still not able to get through both or there is some other way of solving this problem ?

Теги dp, spoj, lcs
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

There is another solution using dynamic programming: dp[start_pos][length]

if(s[i]==s[i+j-1])
	dp[i][j]=dp[i+1][j-2];
else
	dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]);

You can use both of the solutions but you should allocate only dp[3][5001] memory. You can do this because you need only (i-1)th and (i-2)th rows of dp array to calculate i-th row.

→ Ответить