Hello everybody,
I have a really hard problem with Dynamic Programming Bottom-up (table method).
Someone told me I should first do Top-down, then construct the base case, then construct recursion tree, then convert the recursion tree to Directed Acyclic Graph, then do a topological sort on this graph.
But always I get stuck and I can't find the solution.
Can any one help me with good material or write a blog about this like PrinceOfPersia [Algorithm Gym].
Thanks in advance :D.
I learnt bottom-up dp from sheer frustration of multiple RE or TLE due to stack overflow (this is the reason why many of us prefer bottom-up). Therefore, I don't have a source or a tutorial from where I learnt, but I will try to explain the steps I usually take when doing a dp. I am going to illustrate the process with the problem of finding the number of substrings of string s of length l, that are palindromes, for multiple queries of l. For this, I will make a table dpi, j of booleans, that is true if the substring starting at index i and length j is a palindrome and false otherwise. Also, let n = |s|.
The trick is to make the order of the iterations in such a way that you can see that the necessary cases for the current calculation are already calculated.
CATCH IT TOPCODER
The best explanation found so far.Each and everything is included in it!! Happy coding
This link has become forbidden. Can you provide the current active link ?
Here https://web.archive.org/web/20160610084708/http://apps.topcoder.com/forums//robots.txt?module=Thread&threadID=697369&start=0
Your top-down dp function is really a mathematical recurrence. It takes some parameters, and returns an answer in terms of the same dp function. So your goal is to calculate the same function using the same recurrence, but without explicitly using recursion.
In general, your top-down dp function might look something like this:
You can make this code top-down by doing:
What is left for you to do is to decide the right order to loop over the parameters. Sometimes you will want to go from 0 to N, sometimes you will want to go from N to 0. Usually you can decide this by looking at how your "calculate answer" function works.
cache[parameter1 + 1][...]
, then you want to loop parameter1 from N to 0, because that should guarantee that the cache value you're looking for is already calculated.cache[parameter1 - 1][...]
, then you want to loop parameter1 from 0 to N, because that should guarantee that the cache value you're looking for is already calculated.cache[parameter1][...]
, try looking for a hint in the other parameters.That's the general idea of converting a top-down dp into a bottom-up dp.
Example: Take the problem: find the nth fibonacci number.
Top-down dp code:
To turn this in to bottom-up, your code will be something like:
Since the answer depends on
cache[n-1]
andcache[n-2]
, you would want to loop over n in increasing order, to make sure that you've calculated them already.Hope that helps :)
Best way to think about bottom up DP is that it is basically a graph of states. Each update is an "edge" between two states. So as long as you go through the states in the correct order, and consider all the edges, it is almost like a shortest path algorithm.