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 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.

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.

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

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.

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 nelse:return fibonacci(n-1) + fibonacci(n-2)

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