Oh. By "dynamic programming," you just mean evaluating the Fibonnaci
recurrence sequentially rather than recursively.
Dave
On Feb 23, 3:22 pm, Ridvan <[EMAIL PROTECTED]> wrote:
> let A=1, K=11
> The recursive formula:
> NumberOfPaths(11) = 0;
> NumberOfPaths(10)=1
> NumberOfPaths(9)=2;
> NumberOfPaths(x) = NumberOfPaths(x+1) + NumberOfPaths(x+2);
> we are looking for NumberOfPaths(1).
>
> Even if this looks as an streightforward solution it is O(2^n) algo.
> So it is fine for 11 stones but what about 50 000?
>
> The O(n) solution for this problem is:
> define array numofpaths[n];
> numofpaths[11]=0;
> numofpaths[10]=1;
> numofpaths[9]=2;
> Come from the tail.
> for(i=8;i>=1;i--){
> numofpaths[i]=numofpaths[i+1]+numofpaths[i+2];}
>
> print(numofpaths[1]);
>
> assuming the first index of array is 1 not 0;
>
> The simmilar solution for printing the paths.
> Best,
> Ridvan
>
> On Feb 23, 4:16 pm, Dave <[EMAIL PROTECTED]> wrote:
>
>
>
> > Please provide more details.
>
> > Dave
>
> > On Feb 22, 8:11 am, Ridvan <[EMAIL PROTECTED]> wrote:
>
> > > Dinnamic programming problem.
>
> > > Just read any example about it.
>
> > > On Feb 12, 8:13 am, "Abhijeet Singh" <[EMAIL PROTECTED]> wrote:
>
> > > > I have stones numbered from A-K and I have a Frog which can make a jump
> > > > of one stone at a time or two stones at a time but no more then that.
> > > > I will explain , assumes my stones are ABCDEFG.... K
> > > > At any point say A, the frog can jump from A-B or from A-C but not from
> > > > A-D
> > > > or otherwise, when it reaches J, it can only make a hop of 1 as there
> > > > are no
> > > > more stones after that. Frog can not jump backwards.
>
> > > > In how many ways can he reach from A-K, give a recursive formula for
> > > > that.
>
> > > > Print all possible paths that the Frog can choose while moving from
> > > > A-K- Hide quoted text -
>
> > > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
