Dynamic Programming Memory Optimization: Dropping Tables (SPOJ IOIPALIN)

I will be describing in this blog one of the tricks to optimize memory in Dynamic Programming solutions.

**Problem in short**:

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

N <= 5000 , Memory Limit : 16MB

First of all let's discuss solving this problem by Dynamic Programming.

Most of the times, whenever we face a problem about palindromes. The most important thing is to think about the structure of palindrome. It's a string that starts empty or consisting of only 1 letter, then it's extended by adding 2 identical letters one at the beginning and one at the end of the string. Till we just get our palindrome. Our problem here is asking as to insert minimum characters in our string so it just becomes palindrome afterwards.

Of course, the first step of a Dynamic Programming solution is figuring out the recursive function. Imagine that the first letter in our string and the last letter are the same, we can just drop them and say they never existed (That's true! prove it yourself).

If they are different, it's clear that we must insert one letter as we are building the palindrome in the way I mentioned. This letter must be identical to one of them (but which one?). Unfortunately we must try both cases. By saying a letter equal to the first one, it means we should insert the same letter at the end of the string (so now we have a string with identical endings so we can drop both of them), but the difference here from the step above that insertion cost us here 1 operation and in fact we dropped only the first letter. (Think how does that apply to the last letter).

ًThe best way to handle this is recursion (Why?). Because at each step we have a string that we should drop the first letter or the second letter and pick the choice that will lead us to a smaller string with smallest possible remaining steps to achieve our goal. In case the 2 letters are equal, the ultimate choice is just to drop them.

So let us build our recursive function :

How will the function look like (data type, parameters). In terms of computer science (Method signature) ?

int F(int l , int r);

Our function will return the minimum number of characters needed to make the substring starting at the *l*th character and ending at the *r*th character a palindrome.

What will be the base case of our function?

if(l >= r)return 0;

That's true, because an empty string or a string made of only 1 character is a palindrome.

What will be the transitions of our function?

// dropping both ends :if(str[l] == str[r])F(l,r) -> F(l+1 , r-1)// inserting a letter equal to the first letterF(l,r) -> F(l+1,r)// inserting a letter equal to the last letterF(l,r) -> F(l , r-1)

Our function will be like:

int F(int l , int r){if(l >= r)return 0;if(str[l] == str[r])return F(l + 1 , r - 1);return min(F(l + 1 , r) , F(l , r - 1)) + 1;}

It's obvious that we can use Dynamic Programming technique and memorize our answers. We can do that because for a fixed state (l, r) of our functions, our answer will not change. Because all calls with same parameters are solved under the same conditions. (Make the table of memorization yourself).

The problem here is that the table of memorization is int [5000][5000] which costs up to 100MB which is too much for the problem memory limit.

The first thing to observe when we need to optimize memory in a dynamic programming solution is the nature of transitions.

Take a look again please at the transitions of our function, the answer of a substring (L,R). On what does it depend?

It depends on the answer of substring (L+1 , R-1) in case of dropping both ends or the answer of substring(L+1 , R) or the answer of substring (L,R-1).

You can observe that the answer of a string of length K depends on the answers of strings of length K-2 (first case) , and length K-1 (remaining two cases).

Let's change the parameters of our function a little, instead of F(l, r) let's make it F(len , l).

l denoting the start of our substring.

len denoting the length of our substring.

It won't affect our state, because r = l + len - 1. So we haven't changed our state much. Just stored another information which can identify our states. It doesn't matter if you know the nominator and the value of fraction from knowing the denominator and the value (in both cases you know what's the fraction).

Let's rewrite our function but this time, the bottom up (iterative) implementation :

#include<bits/stdc++.h>using namespace std;int dp[5009][5009];string str;int main(){int n;cin>>n>>str;for(int j = 0 ; j < n ; j++)dp[0][j] = dp[1][j] = 0;for(int len = 2 ; len <= n ; len++){for(int l = 0 ; l < n ; l++)dp[len][l] = (1<<30);for(int l = 0 ; l + len - 1 < n ; l++){if(str[l] == str[l + len - 1])dp[len][l] = dp[len-2][l+1];else dp[len][l] = min(dp[len-1][l] , dp[len-1][l+1]) + 1;}}cout<<dp[n][0]<<endl;}

You can notice that for any state dp[len][?]

? refers to any arbitrary position.

for any state dp[len][?] we are only considering states dp[len-1][?] and states dp[len-2][?] (How is that useful?)

We have at the beginning dp[0][?] , dp[1][?] as they represent answers for empty and single character strings. Let's just calculate dp[2][?] (the whole table) and continue on. When we are calculating dp[3][?] do we still need the table dp[0][?] (The answer is No, we mentioned why above) the same goes to dp[4][?] (We don't need dp[0][?] neither dp[1][?]). In fact when calculating the value of dp[x][?] we don't need any of values dp[y][?] (where y < x-2).

As a conclusion, we can calculate the values of our function in increasing order by length. and keeping only the last 2 tables while calculating the current one. After finishing the current one dp[len][?] we can just drop the table dp[len-2][?] and continue on. So we need just 3 tables.

There is something deserves mention, is that we are not able to apply this trick if we are implementing our function the recursive way. Because the recursive way while calculating the answer for a fixed state it may calculates the answer for arbitrary subproblems (sub-states) and like filling a random part of the table. So this is not applicable. While here before proceeding into a deeper level we are sure that we have all the information we need to calculate the answer for the next level fully.

Implementation with clarifications:

#include<bits/stdc++.h>using namespace std;int dp[3][5009];string str;int main(){int n;cin>>n>>str;// handling the empty / single characters strings casefor(int j = 0 ; j < n ; j++)dp[0][j] = dp[1][j] = 0;// iterating through lengthsfor(int len = 2 ; len <= n ; len++){// initiating the table we are going to fillfor(int l = 0 ; l < n ; l++)dp[2][l] = (1<<30);// filling table as describedfor(int l = 0 ; l + len - 1 < n ; l++){if(str[l] == str[l + len - 1])dp[2][l] = dp[0][l + 1];else dp[2][l] = min(dp[1][l+1] , dp[1][l]) + 1;}// dropping the pre-previous table and shifting our tablesswap(dp[1] , dp[0]);swap(dp[1] , dp[2]);// make sure to always initialize your next table before filling// because as you can see we are bringing a table with old values that may affect our answer}cout<<dp[1][0]<<endl;}

Read more…(1023 words)

About the author:

Hussain Kara Fallah

Loading…

Join the discussion. Add a reply…

Post

Table of contents

- Dynamic Programming solution:
- Optimizing Memory:

About the author

Hussain Kara Fallah

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.