//code sketch based on greedy approach.
jumps(int hop,int n)
{
if(hop n)
{
return;
}
if(hop==n)
{
//path found
}
for(i=hop ; in i hop+arr[hop] ; i++)
{
jumps( (i+arr[i])-1 , n);
}
}
@above : call jumps(0,n-1);
On Sat, Jan 28, 2012 at 2:00 PM, atul anand atul.87fri...@gmail.com wrote:
//code sketch based on greedy approach.
jumps(int hop,int n)
{
if(hop n)
{
return;
}
if(hop==n)
{
//path found
Can anyone show me a case where the following greedy algorithm does
not produce the optimal result:
From position i, if you can move to the end, do it
Otherwise make the legal move to location j which maximizes j+arr[j].
Don
On Jan 25, 11:03 pm, Sanjay Rajpal sanjay.raj...@live.in wrote:
Given
@Don:
The solution looks good...
I can see that the greedy choice property is holding.. and its optimal
too...
max (j+a[J]) maximizing is leading us to the farthest possible position,
but.. in the beginning.. i thought.. this will have probs with 0's
but.. couldn't come up an example, for
At first I thought that I needed a special case to avoid zeros.
However, if you can move past a zero to a non-zero, that is always a
preferred move, and if not, a move to a location before the zero which
allows you to move past the zero is also better. If no such move
exists, there is no way to
From position i, move n such that n = arr[i] and n+arr[i+n] is
maximized.
Don
On Jan 25, 11:03 pm, Sanjay Rajpal sanjay.raj...@live.in wrote:
Given an array of integers where each element represents the max number of
steps that can be made forward from that element. Write a function to
return
