Python Data Structures and Algorithms

The tabulation technique

There is a second technique in dynamic programming, which involves the use of a table of results or matrix in some cases to store results of computations for later use.

This approach solves the bigger problem by first working out a route to the final solution. In the case of the fib() function, we will develop a table with the values of fib(1) and fib(2) predetermined. Based on these two values, we will work our way up to fib(n):

    def fib(n):         results = [1, 1]         for i in range(2, n):             results.append(results[i-1] + results[i-2])         return results[-1] 

The results variable is at index 0, and 1 the values, 1 and 1. This represents the return values of fib(1) and fib(2). To calculate the values of the fib() function for ...