### primeprogrammer2021's blog

By primeprogrammer2021, 5 weeks ago, 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. Comments (7)
 » 5 weeks ago, # | ← Rev. 2 →   I would say that a typical DP solution consists of two "parts": coming up with a recursive formula that will solve the problem; 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.
•  » » 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).
 » any problem is a dp problem if you name your array dp ;)