- Divide and conquer
- Dynamic programming
- Greedy algorithm
- Back Tracking
- Brute Force
It's a technique of speeding up recurrent algorithms.
It's applicable in case when:
- it's recurrent
- it has overlapping problems
- input is ordered
Downsides:
- still have not much meaning in solving NP-complete problems
- we don't know sequence which lead us to the result
From stackoverflow.com
So Dynamic programming is a method to solve certain classes of problems by solving recurrence relations/recursion and storing previously found solutions via either tabulation or memoization.
Memoization is a method to keep track of solutions to previously solved problems and can be used with any function that has unique deterministic solutions for a given set of inputs.
When you use memoization you store your data in key-value based data structures.
With tabulation you store all results in a table (array) with index-based access to data.
It's a technique of solving algorithms through separating input on two or more parts.
For example, merge sort, MapReduce.
Some algorithms use random numbers to solve problems. Correctness of using it is proven using statistics.
For example, quick sort, fast exponentiation.
- Back Tracking
stackoverflow.com – What is the difference between memoization and dynamic programming?
stackexchange.com – Is MapReduce anything more than just an application of divide and conquer?
wikipedia – Divide and conquer
khanacademy.org - Divide and conquer algorithms