Consider:
Greedy | Divide & Conquer | Dynamic Programming |
---|---|---|
Optimises by making the best choice at the moment | Optimises by breaking down a subproblem into simpler versions of itself and using multi-threading & recursion to solve | Same as Divide and Conquer, but optimises by caching the answers to each subproblem as not to repeat the calculation twice. |
Doesn’t always find the optimal solution, but is very fast | Always finds the optimal solution, but is slower than Greedy | Always finds the optimal solution, but could be pointless on small datasets. |
Requires almost no memory | Requires some memory to remember recursive calls | Requires a lot of memory for memoisation / tabulation |