How to optimize space for SPOJ AIBOHP

Question

I was doing this particular problem AIBOHP and used a dp approach based on checking the ends of a substring of length i starting from 1. Although my time complexity is fine at O(n^2) but space is taking too much because of which I am getting RTE if I am declaring it dynamically or TLE if I am declaring it as global static which needs to be reduced because the dp size can be 6100*6100 . Any suggestions how to optimize my below code for this purpose .

The problem statement is :

He now asks the doctors to insert the minimum number of characters needed to make S a  palindrome. Help the doctors accomplish this task.
For instance, if S = "fft", the doctors should change the string to "tfft", adding only 1 character.

and my code is :

static int dp[6101][6101];
main()
{
    int tc;
    scanf("%d",&tc);
    while(tc--)
    {
        char s[6102];
        scanf("%s",s);
        int len=strlen(s);
        memset(dp,0,sizeof dp);
        for(int i=1;i<len;i++)
            for(int j=0,k=i;k<len;k++,j++)
                dp[j][k]=(s[j]==s[k])?dp[j+1][k-1]:min(dp[j][k-1],dp[j+1][k])+1;
        printf("%d\n",dp[0][len-1]);
    }
    return 0;
} 

Answer 1

Your Logic is Correct.

I made a change in your code changing static dp[6101][6101] to static short dp[6101][6101]. Yes declaring it as Short. This helps to avoid Memory Wastage and AC.

You can check for yourself !

Answer 2

Your code works ok for me (haven't checked the correctness, but it throws no run time errors and produces a solution immediately on a 6100 length input string).

The page says "Memory limit: 256MB", and 6101*6101*4 is 144 MB. However, there are 2 things I can think of.

First, from my understanding of your algorithm, I don't think it needs the full range of int? Try making dp:

static unsigned short dp[6101][6101];

as this would halve the memory usage. This might already be enough.

Second, you can try dynamically allocating it like this:

int **dp = (int **)malloc(6101*sizeof(int *));
for (int i = 0; i < 6101; i++)
    dp[i] = (int *)malloc(6101*sizeof(int)); 

and replace the memset() call with:

for (int i = 0; i < 6101; i++)
    for (int j = 0; j < 6101; j++)
        dp[i][j] = 0;  

if the static allocation is the problem for some reason (this doesn't save memory). Or combine both approaches.