如何优化 SPOJ AIBOHP 的空间利用

Question

我正在解决这个具体的问题AIBOHP，并使用基于检查长度为 i 的子字符串起始位置为 1 的末尾的 dp 方法。尽管我的时间复杂度在 O(n^2) 范围内，但由于空间占用过大，如果我动态声明它就会出现 RTE，如果我将其声明为全局静态，则会超时，需要减少它，因为 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;
} 

- Kavish Dwivedi

Answer 1

你的逻辑是正确的。

我对你的代码进行了更改，将 static dp[6101][6101] 改为 static short dp[6101][6101]。是的，声明为短整型。

这有助于避免内存浪费并通过测试。

你可以自行验证！

- S J

Answer 2

你的代码对我来说很好用（我没有检查正确性，但它没有运行时错误，并且在输入长度为6100的字符串后立即生成解决方案）。

页面上写着“内存限制：256MB”，而6101 * 6101 * 4是144 MB。但是，我能想到两件事。

首先，根据我对你算法的理解，我不认为它需要完整范围的int类型？尝试使dp：

```python dp = [0] * (2 * n + 1) ```

第二，如果您确实需要更多内存，则可以尝试使用pypy代替python。

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;  

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

- svinja

---

也许可以使用 for (int i = 0; i < 6101; i++) memset(dp[i], 0, 6101*sizeof(int)); 替代双重循环。 - Bernhard Barker