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

I think the dynamic programming state would be dp[i][k] which represents the optimal overall value if we place integer k at position i of A. There are 100 transitions (one for each value for k). If we memoize the states, then, we evaluate each transition once only. So we have 1e2 * 1e5 * 20 operations which is 2e8 operations and should be able to pass the time limit.

I haven't tried out this solution on the judge. But this seems like a sensible solution to me.

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:

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

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.

why abs(B[i] — 1) when A[i — 1] = 1?, I am a beginner so ...

a[i-1]=1 means we consider taking 1 in the previous position and abs(B[i]-1) will give the the abs. diff. between current pos. and the previous one (which we are considering as 1).

It's easy to prove that for all i, the optimal A has either A[i] = 1 or A[i] = B[i]Hmm. Seems intuitive. But I couldn't find a formal proof. Do you mind sharing the proof please?

I know that this was asked 2 years ago, Posting this for new readers

Idea for Proof

Lets say you have values for

`A[i-1]`

and`A[i+1]`

, you need to find`A[i]`

such that`A[i]`

belongs to`[1,B[i]]`

and`|A[i]-A[i+1]|`

+`|A[i]-A[i-1]|`

is maximized, draw the number line and mark`A[i-1]`

and`A[i+1]`

, you then have to analyzed few cases then you will see that in every case either`A[i]==B[i]`

or`A[i]==1`

gives the maximum.