Dynamic Programming

There are two essential features that let us know that dynamic programming can be applied:

1. recursive sub-structure
2. overlapping sub-problems

memorisation - when we evaluate an application, remember the result so that we don't have to evaluate it again.

One way to apply memorisation would be to maintain a table of applications that have been evaluated. For every new application, we check first to see if we have it in the table. Else we have to calculate it and store the result.

Dynamic programming applies this principle in a cleverer way, if we know what applications have to evaluated then we can order them in such a way that repetition is avoided and no checking is required.

Fibonacci example

Recursive fib(k) = fib(k-1) + fib(k-2) if k>1, else =1 if k <=1.

Dynamic Programming fib(k) = d_fib(k,1,1)

def d_fib(k,x,y) if k=0 return 1 else return d_fib(k-1, y, x+y)

Another way to do it would be go set up a table and compute all of the values in the table in such a way that the newly calculated values only depend on other previously already calculated values in the table.

This is what they do with the lowest common sub-sequence and 0-1 knapsack problem in the lectures.

Why was the dynamic solution to the 01 knapsack problem not polynomial time? Is it not an NP-hard problem? Is the complexity polynomial?

With big O what is n? (the size of the input) What is w? (the maximum weight) What is the size of w as an input? log(w).. The table grows exponentially as w grows.