Dynamic programming is a method for developing algorithms that are improvements over traditional recursive algorithms. Richard Bellman introduced and developed it into a formal methodology. Dynamic programming applies to problems —
For example, generating the Fibonacci series is a good candidate for dynamic programming, because —
There are two approaches to dynamic programming.
Top-down approach (memoization): This approach is regular recursion with an added memoization step. Memoization enables the reuse of solutions to sub-problems from past computations. Pure functions simplify this memoization as their output depends solely on the input.
This approach is comparatively slower than bottom-up as recursion is still an expensive operation in itself.
Bottom-up approach (tabulation): This approach works by identifying the sub-problems as the building blocks of the higher-level problems. By solving the lowest-level problems first and tabulating their solutions, the algorithm can directly evaluate solutions to higher-level problems.
This approach is faster compared to the top-down approach as each sub-problem is only encountered once.