Please read the new rule regarding the restriction on the use of AI tools. ×

samearth's blog

Help in Sherlock And costs

By samearth, history, 4 years ago, In English

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

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

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

      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.

      → Reply