This is true when memoization is being used to merely improve
asymptotic efficiency of a single computation. (As you say, it's a
nice technique for DP, when you can often just remember one or a few
previous rows of results.)
However this is not the only use. General memoization maintains
values persistently. In this case memoized fib(n) will cost O(n) for
the first call. Afterward any call for fib(i), i <= n will run in
constant time. If there are many similar-valued calls to fib, this is
a big deal.
On Oct 11, 7:15 pm, Vandana Bachani <vandana....@gmail.com> wrote:
> Hi Arvind,
> For the fibonacci series, we need to memoize only the the last 2 fibonacci
> numbers.
> We can even avoid recursion... So our regular fibonacci algorithm is the
> simplest example of a dynamic programming algorithm with memoization.
>
> To find nth fibonacci number:
>
> int p = 0, q = 1, f;
> for (int i = 1; i <= n; i++)
> {
> f = p + q;
> p = q;
> q = f;
>
> }
>
> But as gene mentioned, in complex programs involving dynamic programming we
> might need to access more than 1 or 2 previously obtained values. To reduce
> the burden of recalculating old values, we preserve them in a
> hash/table/array, as the case might be and access them directly from there.
> One of the most important properties of dynamic programming is that the
> solutions to sub-problems are reused, which can be achieved with
> memoization.
>
> -Vandana
>
>
>
> On Tue, Oct 11, 2011 at 3:17 AM, arvind kumar <arvindk...@gmail.com> wrote:
> > ya ya,realy sorry..typo!its MEMOIZATION.
>
> > On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg <ankurga...@gmail.com> wrote:
>
> >> Memoization ?
>
> >> On Mon, Oct 10, 2011 at 6:34 PM, arvind kumar <arvindk...@gmail.com>wrote:
>
> >>> Can anyone tell me how to go about with the memorization technique to
> >>> retrieve values from already stored values,in case of eveluating
> >>> sequences(fibonacci series,etc).?
>
> >>> --
> >>> 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
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> 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
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > 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
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- 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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
