Abinash's blog

LightOJ 1025 — The Specials Menu DP Problem
By Abinash, 10 years ago, In English

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 .

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your great help. Now I understand .

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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...

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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....

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply