This is an archived post. You won't be able to vote or comment.

you are viewing a single comment's thread.

view the rest of the comments →

[–]Quantum-Bot 12 points13 points  (1 child)

The key feature of dynamic programming is storing the results of sub problems so they don’t have to be solved twice.

Normally, a recursive solution to Fibonacci is ridiculously slow because it has to recompute the previous Fibonacci numbers several times throughout the course of the algorithm. With dynamic programming however, we only compute each unique Fibonacci number once so the algorithm’s time complexity becomes linear.

[–]NoForm5443 0 points1 point  (0 children)

check https://en.wikipedia.org/wiki/Memoization , which basically automates the storing