- Memoization is when you store previous results of a function call (a real function always returns the same thing, given the same inputs). It doesn’t make a difference for algorithmic complexity before the results are stored.
- Recursion is the method of a function calling itself, usually with a smaller dataset. Since most recursive functions can be converted to similar iterative functions, this doesn’t make a difference for algorithmic complexity either.
- Dynamic programming is the process of solving easier-to-solve sub-problems and building up the answer from that. Most DP algorithms will be in the running times between a Greedy algorithm (if one exists) and an exponential (enumerate all possibilities and find the best one) algorithm.
- DP algorithms could be implemented with recursion, but they don’t have to be.
- DP algorithms can’t be sped up by memoization, since each sub-problem is only ever solved (or the “solve” function called) once.
VietMX Staff asked 3 years ago
