### HitmanBBa's blog

By HitmanBBa, history, 8 years ago, 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]. dp, Comments (5)
 » 6 years ago, # | ← Rev. 3 →   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|. Think of a data that is common to all test cases, that is given in the problem. In this problem, you know that dpi, 1 = true for all i, as all substrings of length 1 are palindromes. Also, you know that dpi, 2 = true if and only if si =  = si + 1. You should write all of these values in your dp table before anything else. Think of the transition of the graph. If you have for sure one data, then what does it happen? For example, in this problem, you know that for j > 2, dpi, j = true if and only if si =  = si + j - 1 and dpi + 1, j - 2 = true. If you master top-bottom dp, this should be easy, as the transitions are the same. Figure a way to make the iteration in such a way that when you want to make a transition, all the elements necessary to calculate them are already calculated. Normally, the transition gives you the answer for this. In this case, the transition tells me that you need to calculate the answer for length l - 2 before attemping to calculate the answers for length l. Then, the following code works correctly: \\ After stating the values of length 1 and 2 for(int j=3;j<=n;j++){ for(int i=0;i
 » 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: int dp(parameter1, parameter2, parameter3...) { if (base case) { return some answer } else if (visited[parameter1][parameter2][parameter3][...]) { return cache[parameter1][parameter2][parameter3][...]; } else { calculate for this dp state (this is called the recurrence) store answer in cache[parameter1][parameter2][parameter3][...]; return cache[parameter1][parameter2][parameter3][...]; } } You can make this code top-down by doing: identify base cases calculate base case answers put base case answers in cache[][][...] for each parameter1 in some range: for each parameter2 in some range: for each parameter3 in some range: ... calculate answer for this dp state (with the same recurrence) store answer in cache[parameter1][parameter2][parameter3][...]; 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. If answer depends on 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. If answer depends on 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. If answer depends on cache[parameter1][...], try looking for a hint in the other parameters. Same thing for any other parameter 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: int dp(int n) { if (n == 0 or n == 1) return 1; if (visited[n]) return cache[n]; cache[n] = dp(n-1) + dp(n-2); return cache[n]; } To turn this in to bottom-up, your code will be something like: // base cases: cache = 1; cache = 1; for each n in some order: cache[n] = cache[n-1] + cache[n-2]; Since the answer depends on cache[n-1] and cache[n-2], you would want to loop over n in increasing order, to make sure that you've calculated them already.Hope that helps :)