After formulating the recurrence for a dynamic programming algorithm, how can we fill in the table?

Question

A recurrence relationship is an imperative part of a dynamic programming approach.

I was solving the problem of finding the minimum number of edits needed to create a palindromic string.

dp[i, j] = min(
               dp[i+1, j-1] if s[i] == s[j],
               dp[i+1, j-1] +1,
               dp[i+1, j] +1
               dp[i, j-1] +1
)

After formulating the recursive equation, it's trivial to implement a top down approach that uses a hash table.

What I can't understand is how to use this recursive formula to build the solution table from the bottom up. By doing it bottom up, we save memory as we don't need to compute a recursion stack. It's also a bit more elegant to do it bottom up.

So, to flip this recurrence and start from the bottom up. We need to consider substrings that have a length of 1 to length of N. However, I'm struggling with creating these for loops appropriately.

My question: Once formulating the top-down recurrence for a DP problem, how do we flip it and use a bottom up approach to fill in the subsolution table?

Matt Timmermans · Accepted Answer · 2018-01-21 20:54:59Z

2

In your recursive formula, the value for each cell dp[i,j] is calculated the values with larger i and/or smaller j.

If you want to calculate the cells bottom-up, you just have to visit them in an appropriate order, so that the cells you need for every dp[i,j] are already done by the time you get there.

Since you need all the larger is to be done, visit cells in order of decreasing first coordinate, and since you need all the smaller js to be done, visit cells in order of increasing second coordinate. It doesn't really matter which coordinate is in the inner or outer loop.

answered Jan 21, 2018 at 20:54

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

DAle · Accepted Answer · 2018-01-21 20:24:56Z

1

You should fill it starting from 'smallest' problems to 'largest'.

We need to consider substrings that have a length of 1 to length of N

Yes, that's right. Let's iterate through the lengths in the outer loop:

for len in range(1, n+1):
     for i in range(n-len+1):
         dp[i][i+len-1] = ...

answered Jan 21, 2018 at 20:24

DAle

9,1922 gold badges28 silver badges48 bronze badges

8 Comments

彼得名姓 Over a year ago

Cool. Though I don't quite understand the second loop. for i in range(n-len+1): That is, I don't understand why this is here.

彼得名姓 Over a year ago

Also - should it be for i in range(n-len): why did you add the plus one?

DAle Over a year ago

@彼得名姓, i is a start of the interval of length len, the end of this interval is i+len-1. But we also need to prevent going out of the array bounds, thus we need to limit i with n-len.

DAle Over a year ago

@彼得名姓, we need to go through all values from 0 to n-len inclusively. That's why range(n-len+1), we are talking about python's range(), right?

彼得名姓 Over a year ago

I suppose a related question: how do we track the solution during this numerical optimization process? That is, suppose I wanted to find what this solution was. I suppose I should make this a separate question.

|

Collectives™ on Stack Overflow

After formulating the recurrence for a dynamic programming algorithm, how can we fill in the table?

2 Answers 2

Comments

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related