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

Need help solving Probelm
Автор peaceful_warrior, история, 10 лет назад, По-английски

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.

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

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

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

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

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

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

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

      → Ответить