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.
 
 
notes/classes/algorithms/dynamic_programming_basics.md

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.

coin_row_problem

change_making_problem

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