Dynamic Programming

My understanding of dynamic programming is to store values to avoid recursion. This will improve the running time of an algorithm from exponential to linear.

Here's some excerpts I read from the book Algorithms in C++ : parts 1 - 4 : fundamentals : data structures : sorting : searching

1. Bottom-up DP:
    Instead of recursively call the functions and get the result Rn, we get Rn by computing all the function values in order starting at the smallest, using previously computed values at each step to compute the current value Rc.

2. Top-down DP:
    An even simpler view of the technique that allows us to execute recursive functions at the same cost as ( or less cost than) bottom-up DP in an automatic way.
    We instrument the recursive program to save each value that it computes (as its final action, ie at the next to last line of the recursive function ), and to check the saved values to avoid recomputing any of them (as its first action, ie, in the first line of the previously recursive function). It's also sometimes called memorization.

We can use bottom-up DP any time that we use the top-down DP, although we need to make sure that we compute the function values in an appropriate order, so that each value we need has been computed when we need it.

In top-down DP, we save known values. In bottom-up DP, we precompute them. We generally prefer top-down to bottom-up DP for:

1. It's a mechanical transformation of a natural problem solution. (Less code change)
2. The order of computing the subproblems takes care of itself
3. We may not need to compute answers to all the subproblems.