Glossary

# Dynamic Programming

## Dynamic Programming

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 —

- that are composed of smaller and simpler sub-problems.
- whose solutions are combinations of the solutions of its sub-problems.
- whose sub-problems overlap with each other.

For example, generating the Fibonacci series is a good candidate for dynamic programming, because —

- F[n] can be be broken down into subproblems F[n-1] and F[n-2].
- F[n] is the sum of F[n-1] and F[n-2].
- F[n-1] itself depends on F[n-2], (and also F[n-3], on which F[n-2] depends).

### What are the two approaches to dynamic programming?

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.

### Write clean and secure code with DeepSource

Powerful static analysis that takes 5 minutes to set up and helps you fix code health and security problems on every pull request.