primeprogrammer2021's blog

Is Fibonacci a DP problem ?
By primeprogrammer2021, 2 years ago, In English

Someone said, " Dynamic Programming is easy to learn, but difficult to master. And by "learn" I mean that you know some basic theory and have solved a DP problem. If you know how to find Fibonacci numbers in O(n) time, then yes, you know DP ".

I was wondering that Fibonacci is so easy that should it be even considered a DP problem ?

Like, when I was given the formula fib[i] = fib[i-1] + fib[i-2] , I was not even told that this is DP.

What are your thoughts ?

P.S.: If someone can suggest how to master DP, it would be helpful.

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
2 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Formally, it is a DP problem, just very trivial.

I'll allow myself some self-advertisement and say that I have a series of post on DP that I think beginners need to read:

Dynamic Programming: Prologue

Two Kinds of Dynamic Programming: Process Simulation

How to solve DP problems: Regular Approach

I'll probably add more in the near future.

→ Reply
»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

As is well known, you can solve every problem using DP, and Fibonacci is a DP problem.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

I would say that a typical DP solution consists of two "parts":

  1. coming up with a recursive formula that will solve the problem;
  2. using memoization — i.e. never calculating the same value twice.

Introductory tutorials usually teach that (2) is the "essence" of what DP is, and while that may be kind of true, it's pretty unfair — because solving part (1) is what takes all the effort. Memoization can be done by anyone immediately after hearing about it and there's a good chance that you've independently thought of this before even learning DP. Coming up with the recursive formula however is pretty unintuitive for beginners and learning how to do that is really what learning DP is all about.

Fibonacci in particular is kind of cheating because you're not even coming up with a recursive formula to solve a problem, you're already given a recursive formula that defines a sequence of numbers and you simply need to calculate that sequence. So you're bypassing the hard part entirely.

It's also notable that some things that are often called DP don't need (2) at all. Memoization is unnecessary for what is commonly called "tree DP".

So I would say that Fibonacci may technically be a DP problem, but in practice, not really. Knowing how to calculate it in $$$O(n)$$$ has little to do with the hard part of solving any real DP problem.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Apologies for nitpicking, but computing Fibonacci numbers using DP is $$$O(n^2)$$$, since $$$F_n$$$ has $$$O(n)$$$ bits (it is $$$O(n)$$$ to compute them modulo something fixed, though).

    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

any problem is a dp problem if you name your array dp ;)

→ Reply