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

Автор mkmeden, история, 2 года назад, По-английски

https://www.hackerrank.com/challenges/tutzki-and-lcs/problem

I ve been trying to solve this for hours and could'nt find any understandable online solution, Can anyone explain the logic and code behind this problem.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You just calculate the $$$LCS$$$ as you do.
Let $$$dp1[i][j]$$$ denotes the $$$LCS$$$ of the suffix starting from $$$ith$$$ and $$$jth$$$ index of string $$$a$$$ and $$$b$$$ respectively.
And $$$dp2[i][j]$$$denotes the $$$LCS$$$ of the prefix till $$$ith$$$ and $$$jth$$$ index of string $$$a$$$ and $$$b$$$ respectively.

Now assume we are adding a character before $$$ith$$$ index of string $$$a$$$ to match it with $$$jth$$$ index of string $$$b$$$. Think of the condition for this pair of indexes to contribute to the answer.

Condition

If we implement that condition directly, then it will overcount. Think why is it so?

Reason
How to fix it?
Code
  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Thank you so much brother. I understood your explanation.

    My Code