codemode's blog

By codemode, history, 5 weeks ago, In English,

This is a problem from a past hiring contest of Hackerrank. We are given an array which contains at max 10^4 elements. Total cost is defined as the sum of absolute difference of the old value of the element and the new value of the element.

Ex: 10 6 3 2 2000

Minimum Cost: 11

1st element 10 can be changed to 6. Cost = abs(10 — 6) = 4.

3rd element 3 can be changed to 6. Cost = abs(3 — 6) = 3.

4th element 2 can be changed to 6. Cost = abs(2 — 6) = 4.

So total cost = 11

Range of elements: [1, 10^9]

How can I apply dynamic programming to solve it? Thanks :-)

Tags #dp
 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by codemode (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it