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 .

8 Years
Discussion Span
Last Post by 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?). ;)


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
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


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. . .

Edited by Adak: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.