Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Is there a fundamental difference between Top down and Bottom up Dynamic programing?

Meaning, 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?

share|improve this question
add comment

migrated from math.stackexchange.com Jul 8 '12 at 0:39

This question came from our site for people studying math at any level and professionals in related fields.

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.