5

我正在做这个特殊的问题AIBOHP并使用了 dp 方法，该方法基于检查从 1 开始的长度为 i 的子串的末端。虽然我的时间复杂度在 O(n^2) 时很好，但空间占用太多，因此我如果我动态地声明它，我会得到 RTE，或者如果我将它声明为需要减少的全局静态，因为 dp 大小可以是 6100*6100 ，我会得到 RTE。任何建议如何为此目的优化我的以下代码。

问题陈述是：

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;
}
4

2 回答 2

3

你的逻辑是正确的。

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

你可以自己查！

于 2013-06-22T10:49:43.407 回答
1

您的代码对我来说可以正常工作（尚未检查正确性，但它不会引发运行时错误并立即在 6100 长度的输入字符串上生成解决方案）。

该页面显示“内存限制：256MB”，6101*6101*4 为 144MB。但是，我能想到两件事。

首先，根据我对您算法的理解，我认为它不需要全方位的int? 尝试制作dp：

static unsigned short dp[6101][6101];

因为这会使内存使用量减半。这可能已经足够了。

其次，您可以尝试像这样动态分配它：

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

并将 memset() 调用替换为：

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

如果由于某种原因静态分配是问题（这不会节省内存）。或者结合这两种方法。

于 2013-06-21T18:47:38.013 回答