Dynamic programming
Fibonacci sequence

Using dynamic programming in the calculation of the n th member of the Fibonacci sequence improves its performance greatly. Here is a naïve implementation, based directly on the mathematical definition:

Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:

In particular, fib(2) was calculated three times from scratch. In larger examples, many more values of fib, or subproblems, are recalculated, leading to an exponential time algorithm.

Now, suppose we have a simple map object, m, which maps each value of fib that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only O (n) time instead of exponential time (but requires O (n) space):

This technique of saving values that have already been calculated is called memoization; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values.

In the bottom-up approach, we calculate the smaller values of fib first, then build larger values from them. This method also uses O(n) time since it contains a loop that repeats n − 1 times, but it only takes constant (O(1)) space, in contrast to the top-down approach which requires O(n) space to store the map.

In both examples, we only calculate fib(2) one time, and then use it to calculate both fib(4) and fib(3), instead of computing it every time either of them is evaluated.
change_case:english_capital