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

LightOJ 1025 — The Specials Menu DP Problem
Автор Abinash, 10 лет назад, По-английски

Problem : The number of ways one could remove letters from a particular word so that it would become a palindrome.Two ways that differ due to order of removing letters are considered the same. And it can also be the case that no letters have to be removed to form a palindrome.

I am trying to solve this problem . But my solution gives wrong answer . Then I found a solution that works here. But don't understand the recurrence . Something like this ..


ll rec(int i, int j)
{
    if(j < i) return 0;
    if(i == j) return 1;
    ll &ret = dp[i][j];
    if(ret != -1) return ret;
    if(str[i] == str[j])
        return ret =  1 + rec(i+1, j) + rec(i, j-1);
    else
        return ret = rec(i+1, j) + rec(i, j-1) - rec(i+1, j-1);
}

I don't understand why subtract rec(i+1, j-1) ? For order of removing letters are considered the same, means we count same way 2 times that why subtract ? Please explain the recurrence , thanks in advance .

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

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

I think this way is better for understanding:

if(str[i] == str[j])
   return ret = (1 + rec(i+1, j-1)) + (rec(i+1, j) + rec(i, j-1) - rec(i+1, j-1));
else
   return ret = rec(i+1, j) + rec(i, j-1) - rec(i+1, j-1);

rec(i+1, j) means you remove ith character and rec(i, j+1) means you remove jth character. In both rec(i+1, j) and rec(i, j-1) you will call rec(i+1, j-1). So you count rec(i+1, j-1) twice if you don't subtract it.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for your great help. Now I understand .

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In the first return case why do we calculate rec(i+1 , j-1) ?? Since as described it will be generated by rec(i+1, j) and rec(i, j-)...

    Please explain...

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      let the string from i to j is AAAA, i=0, j=3 . if(condition) is executed.. => char A at i=0, and char A at j=3, form palindrom so +1, => rec(i+1, j-1), calculate any palindrom that can be concatenated with above palindrom... => rec(i+1, j) + rec(i, j-1) — rec(i+1, j-1), calculate same palindroms as in 2nd step but this time not concetenate with palindrom in 1st step. Hope i am right....

      → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm still confused on the recurrence relation here,can you be more specific please? :(

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I hope this explanation makes the solution clear to you. If there is just one character in the string, it's a palindrome. If there are more characters left in the string, you can remove character from left rec(i+1, j) or right rec(i, j-1). But in both recursions you will count rec(i+1, j-1). To avoid counting twice, we subtract it from ret. There is only one case left: when str[i] == str[j], you can keep both characters (do not remove them) and then you should call rec(i+1, j-1) to build the middle and we add one because we never count the palindrome consisting of just these two characters.

      → Ответить