10.2 Dynamic Programming

Question 1

What does the recurrence tree of the dynamic programming version of the Fibonaccia Sequence look like?

Answer 1

Question 2

What is memoization

Answer 2

Caching values so we don’t have to repeat the same process.

Question 3

What is the memoised recursive version of Weighted Interval Scheduling (and runtime)

Answer 3

• Start from last element first: either in set or not, recurse on both cases.
• Runtime O(nlogn)

Question 4

What is the memoised itterative version of Weighted Interval Scheduling (and runtime)

Answer 4

• Building way up from start. Last element (of current starting set) is either in or not. We have already cached the values, so continue.