Dynamic Programming, greedy algorithms

Question 1

What is the gist of memoization?

Answer 1

Solve a subproblem
store the answer
if we come to this subproblem again use the answer in the dictionary

Question 2

What is the runtime of computing nth Fibonacci when using dynamic programming?

Answer 2

O(n)

Question 3

What steps should you go through when solving a dynamic programming problem?

Answer 3

1. define subproblems
2. guess (part of solution) - possible solutions to check
3. relate sub problem solutions - what is the recurrence relation
4. recurse and memoize or build a DP table bottom up
5. solve the original problem