av
BAN USER
Comments (2)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Use DP. The following expression seems to work:
A is the input array.
OPT[i] is the optimal cost to generate a sorted array after having looked at the array elements from 0 to i.
OPT[i] = A[i-1] if (A[i] >= A[i-1]) else:
min (
(OPT(i-i) + A[i]),
(OPT[i-1] + (A[0]+A[1]+...A[i-1] - (i-1)*A[i]))
)
The first expression is the cost of deleting the element at position i. The second expression is the cost of decrementing all the elements from 0 to i-1 to make them equal to A[i].
This approach requires only one traversal of the array. You can keep track of A[0]+A[1]+...A[i-1] in a variable as the array A is traversed.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
You're right when you say that the array is not required. But, it is still a dynamic programming solution because
- av January 17, 20121) it uses the result of sub-problem(s) in order to calculate the final result.
2) We memoize the result of the smaller sub-problems in order to generate the result of bigger problems.