Dynamic programming

As with many computer science algorithms and techniques, dynamic programming has a mathematical background. The concept of dynamic programming was conceived in the 1940s as a mathematical optimization technique.

There are two main ways of applying dynamic programming to a problem: one is called memoization and the other is the bottom up approach.

A prerequisite for dynamic programming is that the problem has an optimal substructure and overlapping subproblems.

Memoization usually involves coming up with a recursive algorithm for the problem and then, making  use of the already calculated results in the recursion so that the number of recursive calls are reduced significantly.

The bottom up approach involves coming up with the solution for the subproblem and then building the results in a bottom up way  by storing the results in a table. The result of this usually ends up in the last element of the table.

A common example for dynamic programming is the fibonacci series problem. The fibonacci series is defined as a number at index n being the sum of the numbers at the previous two indices in the series: n-1 and n-2. The base case is that the series always starts with 1, 1, 2,…

Using memoization, the solution to the fibonacci series problem is as follows:

memo = {}

def fibonacci(n):
    global memo

    if n in memo:
        return memo[n]

    if n <= 2:
        return 1

    f = fibonacci (n-1) + fibonacci (n-2)
    memo[n] = f
    return f

Using the bottom up approach, the solution to the fibonacci series problem is as follows:

def fibonacci(n):
    memo = {}

    for i in range(n):
        if i<=1:
            memo[i] = 1
            continue

        memo[i] = memo[i-1] + memo[i-2]

    return memo[n]