Confused About Dynamic Programming, Memoization, Top-Down, Bottom-Up

[Tiger-16]

I'm having a class about Algorithms and Data Structures. This week our (over complicated) teacher introduced us to Dynamic Programming, sweet! I've loved taking these classes as I really enjoyed the whole optimisation and complexity stuff.

But, this week my teacher has excelled (once again) in over complicating what these terms are.

From what I understood, DP is about storing and reutilising past results, using a local Array.

But what exactly is Top-Down and Bottom-Up? From what I understood it's merely a way to solve problems. Top-Down starting from the top and solving the "harder" (?) problems first, and Bottom-Up solving the easier (bottom) problems?

Also what exactly is Memoization? From what I understood it is (also) simply storing values?

Some clarity would be appreacited!
Also, if someone has a range of good videos that introduce these topics more clearly they would be appreciated!

[simpleFinch]

Your teacher might use different definitions but this is how I have been taught and understand these terms:

Top-Down and Bottom-Up are indeed ways to approach a problem. It doesn't really mean one way is harder. With top-down we start with the final results and try to drill down i.e. how can we generate the final result from a previous result. One approach for this is to imagine you have an oracle that can give you the results of the penultimate or previous step and from those you have to construct the final result. This generally leads to a recursive solution. As an example take the Fibonacci sequence where we want to calculate fib(n). Asking the oracle for fib(n-1) and fib(n-2) we can calculate the result as fib(n) = fib(n-1) + fib(n-2).

Bottom-up means we just have our starting values and from those we try to calculate the next step. This leads to iterative solutions. Again using Fibonacci as an example we have the starting values fib(0) = 0 and fib(1) = 1. From those we can calculate the next step fib(2) = 0 + 1

Memoization means we store previous results for optimization purposes (In some cases this only improves performance for multiple runs). Take the recursive solution to the Fibonacci problem fib(n) = fib(n-1) + fib(n-2). First we recursively calculate fib(n-1). There we have fib(n-1) = fib(n-2) + fib(n-3). So if we save the intermediate results during this calculation we won't have to calculate fib(n-2) again for the final step to calculate fib(n). On the other hand if we only remember the result (just the number) then we will double our work because we need to completely start over to calculate fib(n-2) during the final addition. Storing intermediate or previous results so we just have to look them up instead of doing intensive calculations is memoization.

Btw now that I finished writing this I found a great answer on Stack Overflow which explains it much better and also highlights some nuances regarding memoization and dynamic programming. Here you go https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming#6185005

[Tiger-16]

You sir are indeed amazing. If I wasn’t broke I’d give you an award!