-2

I'm talking about the problem of calculating the n-th fibonacci number. Some users here say that it is in fact a DP problem, (please see the first answer to this question and the comments of the same answer What is dynamic programming?) but others say that it isn't because it doesn't optimize anything and because of other reasons, so is it or not?

Cœur
  • 37,241
  • 25
  • 195
  • 267
carl
  • 29
  • 1
  • 2
    This question appears to be off-topic because it is not about programming. – duffymo Jul 25 '14 at 17:14
  • 2
    there's a simple algebra formula to calculate any fibonacci value, so "dynamic" program is not needed: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression – Marc B Jul 25 '14 at 17:14
  • 2
    I'm assuming "dp" to mean "dynamic programming." If that is the case, then yes; it is a programming question. It's just not a very good one. Original Poster needs to perform his own analysis for his homework assignment. Certainly, that is what his instructor expects of him. – K. Alan Bates Jul 25 '14 at 17:15
  • @K.AlanBates I don't have any assignment , i just want to know – carl Jul 25 '14 at 17:19
  • Then you could have performed at least a google search before coming here. If you know what dynamic programming is and you know what a fibonacci sequence is, then you already know your search criteria. If you really must have an answer to the question as posed: "maybe; it depends on your requirements." – K. Alan Bates Jul 25 '14 at 17:21
  • @K.AlanBates The existence of info elsewhere on the net via Google does not preclude it from being appropriate on SO. It might be a bad question, but not just because it can be found via a Google. SO is a resource, and saying something shouldn't exist because its available in Google, is like saying some Wikipedia page should be deleted because it can be found elsewhere on the net via Google. – AaronLS Jul 25 '14 at 17:24

1 Answers1

0

From Wikipedia page of dynamic programming,

 var m := map(0 → 0, 1 → 1)
 function fib(n)
   if key n is not in map m 
       m[n] := fib(n − 1) + fib(n − 2)
   return m[n]

This technique of saving values that have already been calculated is called memoization; this is 
the top-down approach, since we first break the problem into subproblems and then calculate and 
store values.

So, it's one of the techniques used to get the Nth number in the sequence.

EDIT - For the added question, memoization is a form of DP.

Swapnil
  • 8,201
  • 4
  • 38
  • 57
  • Thanks for replying . But you are using a technique of DP to solve the problem , but does that make the Fib. series a DP Problem? – carl Jul 25 '14 at 17:30
  • There's nothing like a DP problem. The problems which can be solved using this technique can be called as DP problems. You can call this a DP problem if you want. But many DP problems also have a non-DP solution too. – Swapnil Jul 25 '14 at 17:31