When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that if satisfied by a recursive algorithm would imply that using dynamic programming will reduce the time complexity of the algorithm? When should I use dynamic programming?

Dynamic programming is useful is your recursive algorithm finds itself reaching the same situations (input parameters) many times. There is a general transformation from recursive algorithms to dynamic programming known as memoization, in which there is a table storing all results ever calculated by your recursive procedure. When the recursive procedure is called on a set of inputs which were already used, the results are just fetched from the table. This reduces recursive Fibonacci to iterative Fibonacci.

Dynamic programming can be even smarter, applying more specific optimizations. For example, sometimes there is no need to store the entire table in memory at any given time.

StackExchange Computer Science Q#2057, answer score: 11