What should you consider when choosing between Top-Down vs Bottom-Up solutions for the same problem?

Two things to consider when deciding which algorithm to use

1. Time Complexity. Both approaches have the same time complexity in general, but because for loop is cheaper than recursive function calls, bottom-up can be faster if measured in machine time.
2. Space Complexity. (without considering extra call stack allocations during top-down) Usually both approaches need to build a table for all sub-solutions, but bottom-up is following a topological order, its cost of auxiliary space can be sometimes reduced to the size of problem’s immediate dependencies. For example: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), we only need to store the past two calculations

That being said, bottom-up is not always the best choice, I will try to illustrate with examples:

1. Top-down only solves sub-problems used by your solution whereas bottom-up might waste time on redundant sub-problems. A silly example would be 0-1 knapsack with 1 item…run time difference is O(1) vs O(weight)
2. you might need to perform extra work to get topological order for bottm-up. In Longest Increasing Path in Matrix if we want to do sub-problems after their dependencies, we would have to sort all entries of the matrix in descending order, that’s extra nmlog(nm) pre-processing time before DP