How to convert Memorization dp solution into bottom up(Tabulation) solution?

[anon75813436]

Can someone tell me how one should design bottom up solution from Memorization solution ?
I can think of Memorization easily but find it difficult to convert into bottom up solution.

[iprakhar22]

Hello,

I will try to show how you can form a 2D dp solution using for loops i.e. bottom up solution. Using this intuition, you can similarly do 1D DP (easier than 2D) or higher dimension DPs

Suppose you already have the recurrence with you. Something like, let’s say :

dp(i, j) = 1 + min(dp(i, j - 1), dp(i - 1, j), dp(i - 1, j - 1))

(Edit Distance DP problem)

Now you want to write a bottom up solution (using for loops). To do so all you need to take care of the for loops and for that I follow a simple trick :

1. I draw a 2D matrix (because 2D dp state)
2. I try to look what states does my state dp(i, j) depend upon. Because we need to process all the states dp(i,j) depends upon before processing dp(i, j) right?
3. Take any point on the matrix (i, j) and draw arrows from the states (i, j) depends upon (as shown in the figure)

So in this case, we need (i-1, j) , (i, j-1) and (i-1, j-1) states to calculate (i, j) state. We can see if we run loops for i and j from 0 to n-1 for both i and j, we will always have calculated the previous states to calculate (i, j) th state.

// Assuming base cases and exceptions are handled
for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
         dp[i][j] = 1 + max(max(dp[i-1][j], dp[i][j-1])), dp[i-1][j-1]);

Handle exceptions like out-of-bound indexing and base cases, it’s not taken care of in the code above.

Take another example. This time a little more complex.

dp(i, j) = max(dp(i, k) + dp(k+1, j)) where i<=k<j 

(It is a variant of a well known problem called parenthesization/matrix chain multiplication)

Suppose we are at dp(3, 5). Now, we would need states (3, 3), (3, 4), (4, 4), (4, 5) and (5, 5) to find out the answer of (3, 5). We can draw that diagram and we see that we need :
3…5 values for i
3…5 values for j

That is, we need values greater than 3 for i and we need values lesser than 5 for j. This means if we need for loop for i in decreasing order and we run for loop for j in increasing order, this whole thing should work out.

// Assuming base cases and exceptions are handled
for(int i = n-1; i >=0; --i)
{
    // j starts from i because i <= j
    for(int j = i; j < n; ++j)
    {
        dp[i][j] = -INF;

        // doesnt matter how we loop through k because we just need to find
        // the maximum of all the values. But i <= k < j , we take care of bounds
        for(int k = i; k < j; ++k)
           dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
     }
}

Again, take care of the base cases and the exceptions that I missed out the code. My motive is to help you learn how to convert a memoization dp to tabulation dp.

It is not possible to draw a 3D table to find out what states the current state depend upon. So you just have to kind of take the intuition and practice on problems. I suggest watching videos from Errichto’s YouTube channel as he usually writes bottom up DPs.

Sorry if I made a mistake. Please correct me if I did. This is my first post.

[anon75813436]

It’s really nice post pal !!!
Thankyou for taking out your time to help.
Thanks again !!!

[iprakhar22]

My pleasure

[hari_aumm]

thanks for the explaination, helped a lot!