On Aug 29, 10:43 am, rahul patil <rahul.deshmukhpa...@gmail.com>
wrote:
> Just read the comments. You will get logic.
> 1> read global variables
> 2> start with main
> 3> read rec (a recursive fn)
>
> The main logic is that whether to keep the no in the final no (by
> decrementing it)
> or to completely remove it.
>
> #include <stdio.h>
I think your code is just the dynamic program for solving this.
Let V be the set of values in the sequence A[1..N].
Then define C(n, m) to be the minimum possible cost of making A[1..n]
into a new non-decreasing sequence B by decrementing and deleting
elements from A with the constraint that all elements of B must be at
most m.
Now it's not hard to give a dynamic program for C. First, notice
that
the only decrements we need to consider are those that take an
element
of A to another, smaller value in A. We don't need to worry about
any
"in between" values. Then we can always define C(n, m) in terms of
C(n-1, _).
C(n, m) = min (
a[n] + C(n - 1, m), // delete n'th element
min_{ v | v \in V \and v <= min(m, a[n]) } a[n] - v + C(n - 1, v)
// all feasible decrements of n'th element.
)
The base case is C(1, v) = a[1] - v for all v | v \in V \and v <=
a[1]. And the final answer must be C(N, max(V)).
So were are building a 2d table where each item requires O(n) work
and
the table has O(n^2) entries for a cost of O(n^3). It's certainly
possible that another formulation could be O(n^2).
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
