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

Автор fatemehkarimi, история, 8 лет назад, По-английски

I had a hard time finding a solution to the problem "Sherlock and cost" [](https://www.hackerrank.com/challenges/sherlock-and-cost/problem)but I wasn't able to solve it. then I searched the whole internet and read the people's code. I understood what they do(i.e understand their code) but I can't understand why this algorithm is true and what is the recursion??

can anyone tell me how does its dynamic approach work?? this is the code I read for this problem

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

»
8 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

It's easy to prove that for all i, the optimal A has either A[i] = 1 or A[i] = B[i]. Therefore you can just keep two values at every step, maximum value such that A[i-1] = 1 and maximum value such that A[i-1] = B[i-1]. The state transitions are trivial.

Edit: State transitions:

Let DP[prev][1] be the one where A[i-1] = B[i-1], and DP[prev][0] the one where A[i-1] = 1.

Now:

DP[curr][1] = max(DP[prev][1] + abs(B[i] - B[i-1]), DP[prev][0] + abs(B[i] - 1));
DP[curr][0] = max(DP[prev][1] + abs(B[i-1] - 1), DP[prev][0] + abs(1 - 1));
  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    I can understand well that each A[i] is either 1 or B[i]. actually, those trivial state transitions are not trivial for me!! I mean I can't understand how these 2 arrays work(dp[i][0] and dp[i][1])

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

      The answer we want is the maximum possible cost(the sum S) if, at any index 1<= i <=n we choose either A[i]=1 or A[i]=B[i].

      So, dp[i][0] is the maximum possible cost of the array A[1..i] if we choose to put A[i-1]=1. And similarly, dp[i][1] will store the best cost we can get of the array A[1..i] if we put A[i-1]=B[i].

      So the answer will be max(dp[n][0] , dp[n][1]).

      We begin by setting dp[1][0] = dp[1][1] = 0 because the sum S is 0 for any array of length 1(Base case for the recurrence formula).

      Then, at each index i(from 2 to n), there are two cases:

      • We choose A[i]=B[i] so, depending on the previous state(i-1), we will compute the answer for this state.We will take the maximum of the two possible choices, either the previous element A[i-1] was put to B[i-1], so that will give us abs(B[i]-B[i-1])+dp[i-1][1].Else(in the case where A[i-1]=1) we will get abs(B[i]-1) + dp[i-1][0].So the answer(the sum S) for our current state (array A[1..i]) will be the maximum of these two.

      • We choose A[i]=1.It's the same, you just change B[i] to 1.

      We just calculate the best possible answer for each A[1..i] using the best answer for A[1..i-1] until we reach A[1..n], that will be the best possible cost S for our entire array.