如何优化SPOJ AIBOHP的空间

Question

我正在做这个特殊的问题AIBOHP并使用dp方法基于检查从1开始的长度为i的子串的末尾.尽管我的时间复杂度在O(n ^ 2)处很好但是空间占用太多因为我我正在获取RTE,如果我动态声明它或TLE,如果我将其声明为全局静态需要减少因为dp大小可以是6100*6100.任何建议如何为此目的优化我的下面的代码.

问题陈述是:

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.

我的代码是:

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

你的逻辑是正确的。

我将您的代码更改static dp[6101][6101]为static short dp[6101][6101]. 是的，将其声明为 Short。这有助于避免内存浪费和交流。

你可以自己检查一下！