How can I solve this problem using dynamic programming?
Increasing all elements but one is equivalent to decrease only that element. Find minimum value m, now for each element x you need to find minumum number of subtractions to go from x to m (change-making problem), since you can use greedy algorithm for coins (1, 2, 5), you can solve this problem in O(n).