Dynamic programming in python

 

What is Dynamic Programming?

Dynamic programming is a problem-solving technique for resolving complex problems by recursively breaking them up into sub-problems, which are then each solved individually. Dynamic programming optimizes recursive programming and saves us the time of re-computing inputs later.

Why is Dynamic Programming efficient? Recursion vs. DP

If the two are so closely entwined, why is dynamic programming favored whenever possible? This is because brute force recursive programs often repeat work when faced with overlapping steps, spending unneeded time and resources in the process.

Dynamic programming solves this issue by ensuring each identical step is only completed once, storing that step’s results in a collector such as a hash table or an array to call whenever it’s needed again. In doing so, dynamic programming allows for less repeated work and therefore better runtime efficiency.

Dynamic Programming Examples

Bottom-Up Dynamic Programming

Not all dynamic solutions work in the same way. Some are built bottom-up while others are built top-down. The distinction can be found in how each begins a problem and how sub-problem results are stored.

Top-down Dynamic Programming

Top-down dynamic programming is the opposite to bottom-up. A top-down solution first looks at the main problem and breaks it into smaller and smaller necessary sup-problems until the base case is reached. This is the most common way of building recursive solutions.

Factorial Problem

import time

import matplotlib.pyplot as plt

def fib(n):

  if n <= 0: # base case 1

    return 0

  if n <= 1: # base case 2

    return 1

  else: # recursive step

    return fib(n-1) + fib(n-2)

numbers = 20