codolove's blog

SAMER08D — DNA Sequences on spoj
By codolove, history, 9 years ago, In English

I was trying to solve this problem on spoj that involves LCS with some other constraints. I have come with a recursive solution which gives correct answer on all cases. But when I try to memoziate it, it gives wrong answer. I am not able to figure out why it gives wrong answer on memoziation. my code is here with explanation.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

With your recursive approach, you will need N*N*K memory to store everything which is a lot, the WA might be a RE due to not having enough space to allocate your arrays.

→ Reply