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
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 getabs(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).