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

Help in Sherlock And costs

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

I am finding a hard time solving Sherlock and Cost. it is given in dynamic programming section but i am not able to think it recursively or in a dp way ..... here's the link for the problem...

https://www.hackerrank.com/challenges/sherlock-and-cost/problem

can anyone tell how to approach the problem .. i know the fact that only 1 or the b[i] would be in the answer.!!!

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

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

You already know the states. Each cell can have two values so, let dp[i][0] be the max sum you can form if the ith no. is equal to 1 and dp[i][1] be the max sum you can form if the ith no. is equal to b[i].

Code
→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    okay i got it. but how do we know that it is optimal? i'm a newbie and having a bit trouble solving it... if u could please tell me

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

      For the ith number, there are 2 cases:

      1) a[i] = 1 : (dp[i][0])
Now a[i-1] can be 1 or b[i-1], consider both cases.
If a[i-1] = 1, dp[i][0] = dp[i-1][0] + abs(1-1);
Else dp[i][0] = dp[i-1][1] + abs(b[i-1]-1);

      Take max of both cases, it will give you the optimal answer for a[i] = 1.

      2) a[i] = b[i] : (dp[i][1])
Do the same in this case.

      PS: If you're unable to get it from my comment, I'd strictly recommend you to first learn dp and then attempt these problems.

      → Ответить