Как оптимизировать пространство для SPOJ AIBOHP

Question

Я делал эту конкретную проблему AIBOHP и использовал подход dp, основанный на проверке концов подстроки длины i, начиная с 1. Хотя моя временная сложность в 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]. Да, объявляю его коротким. Это помогает избежать утечки памяти и переменного тока.

Вы можете проверить сами!

Answer 2

Ваш код работает нормально для меня (не проверял правильность, но это не приводит к возникновению ошибок времени выполнения и немедленно выдает решение на входной строке длиной 6100).

На странице написано: «Предел памяти: 256 МБ» и 6101 * 6101 * 4 - 144 МБ. Однако есть две вещи, о которых я могу думать.

Во-первых, исходя из моего понимания вашего алгоритма, я не думаю, что ему нужен полный диапазон 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; 

если статическое распределение является проблема по какой-то причине (это не сохраняет память). Или объедините оба подхода.