Memoized Dynamic Programming algorithm

[evinda]

Hello! (Wave)

I am looking at the following example of Memoized Dynamic Programming algorithm.

memo={}
Fib(n):
  if n in memo return memo[n]
  if n<=2 F[n]=1
  else F[n]=F[n-1]+F[n-2]
  memo[n]=F[n]
  return F[n]

Could you explain me why we check if $n$ is in memo although memo is a set that contains the values of $F[n]$ and not of $n$? (Thinking)

 

[Nono713]

memo is not a set. It would not be very useful to have a set that contains various Fibonacci numbers, since there would be no way to look up a Fibonacci number by its position in the Fibonacci sequence (remember sets have no notion of order; if I give you a set that contains the first 100 Fibonacci numbers and then ask you to give me the 71st Fibonacci number, the set doesn't help a whole lot).

Here memo is an associative array (also known as a map or a dictionary) which associates any integer $n$ to the corresponding Fibonacci number $F_n$, if it has been computed so far (if not, then $n$ is not inside the array and memo[n] is undefined).

 

[evinda]

memo is not a set. It would not be very useful to have a set that contains various Fibonacci numbers, since there would be no way to look up a Fibonacci number by its position in the Fibonacci sequence (remember sets have no notion of order; if I give you a set that contains the first 100 Fibonacci numbers and then ask you to give me the 71st Fibonacci number, the set doesn't help a whole lot).

Here memo is an associative array (also known as a map or a dictionary) which associates any integer $n$ to the corresponding Fibonacci number $F_n$, if it has been computed so far (if not, then $n$ is not inside the array and memo[n] is undefined).

I see... Thank you! (Smirk)