Is there a fundamental difference between top-down and bottom-up dynamic programming?
In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach just an unwinding of the recurrence in the top-down approach?
To use the bottom up method you need to be able to efficiently determine what the "bottom" is, which usually means you need a heavily constrained problem space. If you know what the lowest level calculations are going to be and the dependency order going upward, it makes sense to iteratively do them in the proper order and store those results. Factorials, naive Fibonacci and the Euler recurrence relation for partitions are all good examples of problems suited to this approach.
Some problems don't have an easily determined bottom or dependency order for the calculations. Chess positions evaluations, for example, are usefully memoized by position, with the evaluation score stored so it need not be recalculated. Positions can recur at multiple levels of the search tree due to move transposition and repetition so saving evaluation results is worthwhile. But there's no way to know what the positions at the lowest levels of the tree are going to be without recursively descending (and taking into account intermediate pruning) so top down is really the only feasible approach.
Top-down approach: This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its sub-problems, and if its sub-problems are overlapping, then one can easily memoize or store the solutions to the sub-problems in a table. Whenever we attempt to solve a new sub-problem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the sub-problem and add its solution to the table.
Bottom-up approach: Once we formulate the solution to a problem recursively as in terms of its sub-problems, we can try reformulating the problem in a bottom-up fashion: try solving the sub-problems first and use their solutions to build-on and arrive at solutions to bigger sub-problems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems. For example, if we already know the values of F41 and F40, we can directly calculate the value of F42.
