it can be done in greedy
#includestdio.h
#includeiostream
#includestack
using namespace std;
int main()
{
int n,i,j,count=0;
scanf(%d,n);
int a[n+1],set=0;
a[0]=-1;
for(int i=1;i=n;i++)
scanf(%d,a[i]);
stackint s;
i=1;
j=n;
while(j!=1)
{
set=0;
for(i=1;i=n;i++)
{
if(j-i=a[i])
{printf(%d,i);
j=i;
here is Working Code Without DP in which we need To Find Out Minimum
Jumps for every Jumps its Finding Maximum Step That Can Be Cover In
A Jump So that No. of Jumps Required is Minimized..
#includestdio.h
int main()
{
int arr[]={1 ,3, 5 ,8, 9, 2, 6 ,7 ,6, 8, 9};
int
http://coders-stop.blogspot.com/2010/12/minimum-number-of-jumps.html
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
@avi
regarding ur statement...
3, 5, 3, 4, 1, 3, 4, 5
in the above, the greedy would take 3 - 5 - 4 ( 3 steps)
whereas DP would take 3, 4 ( 2 steps)
it depends on what you are greedy about... as i had mentioned earlier,
your algorithm should be greedy on how far the value you choose will
let
@svix that is precisely the reason why i gave my greedy approach first and
then the pseudo code and then the example, also I mentioned that greedy can
be be of different *locally optimal policies* so they *may* have a higher
running time than the corresponding DP solution.
regarding your
@avi... i didn't quite fully understand the intent of the comment... u
had initially said greedy would make wrong choices 3-5-4 and hence
give wrong minimum number of jumps while DP would give 3-4... hence i
responded saying that if we go greedy on a different function, greedy
will yield the right
Sry I misunderstood your comment. I don't feel the greedy solution which
you gave will work in all the cases. Will update the thread when I next
sleep over it.
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the
actually, there is a way t do this in greedy... instead of taking the
local maximum value v for an index i, take the local maximum f(v) = i
+ v... this will get you the right answer...more efficient than DP?
that i'm not sure... but average case will be close to linear
On Jan 14, 9:29 pm,
@svix, I think pacific means takes i+v, But it still won't give the
global optimal
@Avi, I am not an expert on greedy algorithm and some problems may be
solved by using greedy. But as far as I understand, the difference
between DP and Greedy is DP makes use of the solution of the
subproblems
@jammy Thanx for the elongated description :)
Yes, I feel I probably gave a DP solution wrongly to the Greedy approach.
But just to clarify, Greedy does not solve any subproblems, it just makes a
locally optimal choice and proceedes towards a global optimal strategy. And
your point that greedy
thinkin abt this again, there may be a slight problem with
straightforward greedy...
note that reaching 0 doesn't let u move forward...
On Jan 15, 12:54 pm, Avi Dullu avi.du...@gmail.com wrote:
@jammy Thanx for the elongated description :)
Yes, I feel I probably gave a DP solution wrongly to
The greedy will always chose the maximum, so iff a 0 is chosen, that implies
one cannot reach the end of the array.
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they
I don't think the inner loop is executing only once . Kindly check it for
this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner loop
you will find that for same values of i(Outer index) inner loop is called.
Its an O(n2) solution .
--
You received this message because you are
I guess u got confused with the comment I wrote, I have added 2 print
statements and now I guess it should be clear to you as to why the code is
O(n). The comment means that each element of the min_steps_dp will be
ACCESSED only ONCE over the execution of the entire program. Hence the outer
loop
@Avi Greedy approach doesn't work since you can't ensure the choice is
locally optimum. Consider 3,9,2,1,8,3. Using greedy alg. would give
you 3,1,8,3 while otherwise DP would give you 3,9,3.
On Jan 14, 6:11 am, Avi Dullu avi.du...@gmail.com wrote:
I guess u got confused with the comment I
@jammy Even I felt the same, but the greedy 'algo' u suggest is actually
IMHO not a greedy approach. You just take each arr[i] and jump *without
deciding a locally optimal policy* . SO, if u were to *see* arr[i] and
*decide* on the optimal policy I feel one would follow d same steps as in a
DP
At each location if the value is k ,
find the largest value in the next k elements and jump there.
This greedy approach works in 0(n^2) and i believe it works. If not can
someone give me a counter example ?
On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu avi.du...@gmail.com wrote:
@jammy Even I
@pacific..
the approach needs a little bit of tuning...
for instance, for the set 9 8 7 6 5 4 3 2 1 1 2, per ur approach, u
will pick 9, 8, 7, 6 etc...
minimum jumps in reality is from 9 to 1 to 2.
On Jan 14, 8:19 pm, pacific pacific pacific4...@gmail.com wrote:
At each location if the value
doesn't greedy approach work here ?
On Sun, Jan 9, 2011 at 8:00 PM, juver++ avpostni...@gmail.com wrote:
It doesn't matter how to make transitions: from current position make all
necessary moves,
or determine all positions from which we can achieve i-th position.
So your method is only the
No, there is a counterexample fot the greedy.
--
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
@juver++ : what is the greedy approach one could take here? I know it would
be wrong, but I tried to come up with a test case for greedy failure, but
realized the greedy policy here will be equivalent to the dp.
@Decipher: your's seems to be a O(n^2) solution. Here in the O(n) version of
it.
It doesn't matter how to make transitions: from current position make all
necessary moves,
or determine all positions from which we can achieve i-th position.
So your method is only the one of possible.
--
You received this message because you are subscribed to the Google Groups
Algorithm
Simple DP, dp[i] - minimum number of steps to reach position i. Then apply
simple transitions: dp[i + step] = min(dp[i + step], dp[i] + 1), step =
a[i].
Something in this way.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
23 matches
Mail list logo
