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.
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.
As is well known, you can solve every problem using DP, and Fibonacci is a DP problem.
"you can solve every problem using DP" already implies every problem is a DP problem.
I would say that a typical DP solution consists of two "parts":
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;)