Dynamic Programming problem

[scholar]

Hello friends,
I have a dynamic programming problem and would like to discuss it here.The problem goes as
Given an integer array A[0....i] convert it to an array of strictly increasing numbers.
The operations allowed are
1)Decrease an element by amount x: cost of operation=x
2)Delete an element k: cost of operation =k
And of course we have to find a solution with minimum cost .

[Adak]

You can't delete an element from an array - they are fixed.

Why don't you post a simple example of what you want to do. Your description is dodgy, (or maybe it's just too early?). ;)

[scholar]

Thanks for reply.
Here is an example.
Suppose the given array is
1 3 2 8 4
We have to convert it to an array in such a way that all elements are in non decreasing order. An example would be
1 2 2 5 4
No that is possible in various manner. The cost for above transformation would be
0+1+0+3+0=4
We have to find the minimum cost for transformation.

Deleting an element here means that position in array will not be considered
Ex: 1 2 2 4
Cost here is 0+1+8+0=9 as we are deleting 8.
hope this makes it clear

[Adak]

Note: non-decreasing == ascending order ;)

Fewest number of comparisons: Insertion sort.
Fewest number of swaps: Selection sort.
No comparisons at all: Counting sort (if the data is ranged OK for it)

So we're not trying to move the values (like using a sort), we're adjusting their values, and counting the cost incurred, until the numbers are in sorted order?

Hmmmmmm. . .