私はこの特定の問題AIBOHPを行っていて、1 から始まる長さ i の部分文字列の末尾をチェックすることに基づく dp アプローチを使用しました。私の時間の複雑さは O(n^2) で問題ありませんが、スペースが多すぎるため、私はdp サイズが 6100*6100 になる可能性があるため、動的に宣言している場合は RTE を取得し、グローバル静的として宣言している場合は TLE を取得しています。この目的のために以下のコードを最適化する方法についての提案。
問題文は次のとおりです。
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;
}