HI Rohit,
Although i haven't checked test many cases also I am not saying
algo is wrong but DP will
always Gives us Optimal Solution, even for large data-set,but
Greedy Will Fail in That Case.I
was aware of the same Greedy Algo/Code That you posted but found
DP
@shashank
acc to me the problem can be done easily using greedy approach
https://ideone.com/dYbUd ( it is your non optimal greedy solution
with just one line added )
couldn't find any case where the above code is giving wrong answer .
if you know any case, please let me know.
I wrote a dp
I can only say that above code is wrong, check this code of mine, I
have tested more cases and all are working,
https://ideone.com/pEBs8
see if you can find any bug in this one .
thanks.
On Sat, Aug 13, 2011 at 8:03 PM, WgpShashank shashank7andr...@gmail.com wrote:
@rohit , I think we will get
ok check this, https://ideone.com/hZboG
there may be bugs in coding, but I'm quite sure that algo is correct
need to check more cases though
but working on all the cases discussed here
is there any proof that greedy won't work in this case?
On Sat, Aug 13, 2011 at 11:03 PM, rohit jangid
A Top Down Memoization DP Algorithm Will be As Follow
Step 1. Declare an array of size N say jump[N];
where ith position indicates the number of jumps requires to reach from
start to this (ith) position in array .
Step 2. Initialize jump[0]=0; indicates to reach oth location form starting
Hi, probably you did'nt got my approach :
A={2,2,3,4,1,1,1,1,1}
first i=0 A[i] = 2
so candidates are A[1] ,A[2]
we choose max(A[1] +1 , 2 + A[2]) = A[2]
now we jump to A[2].
now candidates are A[3],A[4],A[5]
we choose max(A[3] + 3 , A[4] + 4, A[5] + 5)
= A[3]
so now we jump to A[3]
now
int A[100];
int dist[100];
int N;
void findDist(int p, int d)
{
if (d dist[p])
{
dist[p] = d;
for(int i = 0; i p; ++i)
if ((i+A[i]) = p)
findDist(i,d+1);
}
}
int main(int argc, char*
