> Oh. By "dynamic programming," you just mean evaluating the Fibonnaci
> recurrence sequentially rather than recursively.
http://en.wikipedia.org/wiki/Dynamic_programming
Not only this.
The recursive solution is O(2^n) >>> O(n).
Ridvan
On Feb 24, 4:38 pm, Dave <[EMAIL PROTECTED]> wrote:
>
> 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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
