### 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.

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

• -6

 » 5 weeks ago, # |   +39 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: PrologueTwo Kinds of Dynamic Programming: Process SimulationHow to solve DP problems: Regular ApproachI'll probably add more in the near future.
 » 5 weeks ago, # |   +23 As is well known, you can solve every problem using DP, and Fibonacci is a DP problem.
•  » » 5 weeks ago, # ^ |   +1 "you can solve every problem using DP" already implies every problem is a DP problem.
 » 5 weeks ago, # | ← Rev. 2 →   +9 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.
•  » » 5 weeks ago, # ^ |   0 +1, Finding out what dp[i] will represent and the formula associated with it is hard.It becomes easy through experience only, or is there some shortcut ?
•  » » 5 weeks ago, # ^ |   +13 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).
 » 5 weeks ago, # |   +1 any problem is a dp problem if you name your array dp ;)