dynamic programming def fastfib(nmemo {})"""assumes is an int > memo used only by recursive calls returns fibonacci of ""if = or = return tryreturn memo[nexcept keyerrorresult fastfib( - memofastfib( - memomemo[nresult return result figure implementing fibonacci using memo if you try running fastfibyou will see that it is indeed quite fastfib( returns almost instantly what is the complexity of fastfibit calls fib exactly once for each value from to thereforeunder the assumption that dictionary lookup can be done in constant timethe time complexity of fastfib(nis ( dynamic programming and the / knapsack problem one of the optimization problems we looked at in was the / knapsack problem recall that we looked at greedy algorithm that ran in log timebut was not guaranteed to find an optimal solution we also looked at brute-force algorithm that was guaranteed to find an optimal solutionbut ran in exponential time finallywe discussed the fact that the problem is inherently exponential in the size of the input in the worst caseone cannot find an optimal solution without looking at all possible answers fortunatelythe situation is not as bad as it seems dynamic programming provides practical method for solving most / knapsack problems in reasonable amount of time as first step in deriving such solutionwe begin with an exponential solution based on exhaustive enumeration the key idea is to think about exploring the space of possible solutions by constructing rooted binary tree that enumerates all states that satisfy the weight constraint rooted binary tree is an acyclic directed graph in which there is exactly one node with no parents this is called the root each non-root node has exactly one parent each node has at most two children childless node is called leaf each node in the search tree for the / knapsack problem is labeled with quadruple that denotes partial solution to the knapsack problem though cute and pedagogically interestingthis is not the best way to implement fibonacci there is simple linear-time iterative implementation