peaceful_warrior's blog

Need help solving Probelm
By peaceful_warrior, history, 11 years ago, In English

Problem link I have seen the solution but i dont understand how the recurrance relation is dp[i]=dp[i-1]+dp[i-2]+2;

Can somebody explain it to me.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

dp[i] consists of the following:

  1. Any good subsequence of all but the last character (dp[i-1] ways)
  2. Any good subsequence of all but the last two characters ending in the same character as the last one + the last two characters (+ denotes concatenation)
  3. Any good subsequence of all but the last two characters ending in a different character from the last one + the last character (2 and 3 together have dp[i-2] ways since every subsequence of the first i-2 characters falls into exactly one of those categories).
  4. Only the last character
  5. Only the last 2 characters (if i > 1)

So total is dp[i-1] + dp[i-2] + 2

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

    Do you think it is a good idea to write down small cases and try to find a pattern to deduce the recurrence relation?

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Yes, definitely. I solved this problem mostly by looking at the cases for n = 3 and 4. Especially pay attention to the new subsequences that actually use the last character.

      By the way, there's an alternative solution (actually the first one I thought of) that counts the sequences ending with R and B separately. Then, if the ith character is R, dp[i][R] = dp[i-1][R] + dp[i-1][B] + 1 (you can take any red-ending subsequence of n-1 and leave it alone or any blue-ending subsequence of n-1 and add the last character or take just the last character), and dp[i][B] = dp[i-1][B]. If the ith character is B, then dp[i][B] = dp[i-1][R] + dp[i-1][B] + 1, and dp[i][R] = dp[i-1][R].

      → Reply