HitmanBBa's blog

By HitmanBBa, history, 9 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

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|.

  1. 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.
  2. 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.
  3. 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<n;i++){
        dp[i][j]=(s[i]==s[i+j-1] && dp[i+1][j-2]);
        \\ Notice that in this line, dp[i+1][j-2] is already calculated
        \\ as it was calculated two outer iterations ago
    }
}

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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

CATCH IT TOPCODER

The best explanation found so far.Each and everything is included in it!! Happy coding

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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[0] = 1;
cache[1] = 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 :)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.