Dynamic programming is a programming paradigm in which we divide a complex problem into smaller sub-problems. We solve these sub-problems and store the results. Whenever we need to recompute the same sub-problem again, we just used our stored results, thus saving us computation time at the expense of using storage space. This technique of caching the results of sub-problems is known as memoization. Therefore, using dynamic programming allows us to speed up our computations by using memoization, and in some cases, it can bring the computational complexity from exponential to linear, as we will see in the following example.
One of the simplest examples of optimization using dynamic programming is computing the nth member of the Fibonacci sequence. Any term in a Fibonacci sequence is the sum of the last two terms, which can be formally defined as follows:
fib...
