Dynamic Programming

Dynamic programming is an approach to solve algorithmic problems by storing results of a recursive problem to avoid unnecessary repetitive computations

Dynamic programming is an approach to solve algorithmic problems by storing results of a recursive problem to avoid unnecessary repetitive computations. By using a memoized (not memorized! It's called that way because we are using a memo to store the data) solution.

An example is the Fibonacci sequence

The Easy Approach (without Dynamic programming)

def fib(n)
	if n == 1 or n == 2
		result = 1
	else
		result = fib(n-1) + fib(n-2)
	return result

In this example, we need to compute the value for fib(3) two times. This approach has a runtime complexity O(2^n)

With Dynamic Programming

By storing the results of the different Fibonacci numbers, we can avoid having to compute them again.

def fib(n, memo)
	if memo[n] != null
		return memo[n]
	if n == 1 or n == 2
		result = 1
	else
		resulst = fib(n-1) + fib(n-2)
memo[n] = result
return result;

This has a runtime complexity of O(2n+1) = O(n)