# Dynamic Programming

### Dynamic Programming

Dynamic programming is a technique to optimize algorithms by breaking a problem with overlapping sub-problems into smaller sub-problems and then combining the solutions to the sub-problems to solve the larger problem.

### Dynamic Programming

Dynamic programming is both a mathematical optimization method and a computer programming method. It simplifies a complicated problem by breaking it down into simpler sub-problems.

It can be applied to combinatorial and optimization problems such as finding the shortest path between two points or finding the smallest set of objects that satisfies some criteria.

### Dynamic Programming Problem Variable

When solving a problem with dynamic programming, we maintain a dynamic set of variables corresponding to each sub-problem that changes in order to find the overall solution. These variables are called problem variables.

### Recursive Step in Recursive Function

A recursive function should have a recursive step which calls the recursive function with some input that brings it closer to its base case. In the example, the recursive step is the call to `countdown()` with a decremented value.

`def countdown(value):  if value <= 0:    print("done")  else:    print(value)    countdown(value-1)  #recursive step `

### What is Recursion

Recursion is a strategy for solving problems by defining the problem in terms of itself. A recursive function consists of two basic parts: the base case and the recursive step.

### Fibonacci Recursion

Computing the value of a Fibonacci number can be implemented using recursion. Given an input of index N, the recursive function has two base cases – when the index is zero or 1. The recursive function returns the sum of the index minus 1 and the index minus 2.

The Big-O runtime of the Fibonacci function is O(2^N).

`def fibonacci(n):  if n <= 1:    return n  else:    return fibonacci(n-1) + fibonacci(n-2)`

### Dynamic Programming Optimal Substructure

A problem has optimal substructure if its sub-problems have optimal solutions that constitute the problem’s optimal solution. This type of problem can be solved using dynamic programming.

0