You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

####
972 B

972 B

# Dynamic Programming Basics

## Date: 04-04-22

#### Class: algorithms

Dynamic programming is a technique for solving something that has many overlapping subproblems. Instead of solving these problems repeatedly, we record the results and use them in solving the larger problem.

Given the fibbonaci sequence, solving recurively would be an exponential problem
$$
F (n) = F (n − 1) + F (n − 2)
\ \ f(0) = 0
\ \ f(1) = 1
$$
*a recurrence_relations for the fibbonaci sequence*

however, if we record the solutions somewhere, it can reach a polynomial big_o rather than the exponential solution.

All of these problems are made much easier by finding an algorithm that allows us to search a datastructure of previous answers to allow for a solution, rather than checking it "by hand" every time.

see also

```
list without id file.inlinks
where file.name = this.file.name
```