このDPプログラムで空間を最適化する方法はありますか？

Question

問題文：

パリンドロームは対称的な文字列です。つまり、左から右、右から左に同​​じように読み込まれる文字列です。あなたは文字列が与えられたときに、文字列に挿入される文字の最小数を決めるプログラムを書く必要があります。一例として、2文字を挿入することにより、文字列「Ab3bd」を回文（「dAb3bAd」または「Adb3bdA」）に変換することができる。ただし、2文字未満の挿入は回文を生成しません。入力文字列N、3≤N≤5000の長さ：

入力

最初の行は、一つの整数を含んでいます。 2行目には、長さNの文字列が1つ含まれています。文字列は、 'A'から 'Z'までの大文字、 'a'から 'z'までの小文字、 '0'から '9'までの数字で構成されます。大文字と小文字は区別されます。

出力

最初の行は、所望の最小数である1つの整数を含んでいます。

リンク問題へ=>http://www.spoj.com/problems/IOIPALIN/

私のソリューション：

#include <iostream> 
#include <memory.h> 
#include <cstdio> 
using namespace std; 

long memo[5010][5010]; 
string s; 
long int n; 
long solve(long i,long j){ 

if(memo[i][j]!=-1){ 
return memo[i][j]; 
} 
if(i>=j) 
return 0; 
if(s[i]==s[j]) 
    return solve(i+1,j-1); 
return memo[i][j]= min(solve(i,j-1)+1,solve(i+1,j)+1); 
} 

int main() 
{ 
ios_base::sync_with_stdio(false); 
long int n ; 
cin>>n; 
cin>>s; 
memset(memo,-1,sizeof(memo)); 

long int a = solve(0,n-1); 
cout << a << endl; 
return 0; 
} 

私は、このコードに "タイムリミットを超え、" 取得しています。これをどうすれば解決できますか？

Answer 1

よくプログラマーになって、その解決策を直接質問するのは悪い習慣です。私は正確なコードをあなたに提供しませんが、私はあなたが問題を解決するのを手伝ってくれます。

これを解決するには、n^2アプローチが必要です。動的プログラミングが必要です。これを達成するには、strの逆の文字列rev_strを作成します。次の擬似コードを見てください。

for(i = 0 to n) 
    for(j = 0 to n) 
     if(i = 0 or j = 0) dp[j][1] = 0; 
     else if(str[i - 1] = rev_str[j - 1]) dp[j][1] = dp[j - 1][0] + 1; 
     else dp[j][1] = max(dp[j][0], dp[j - 1][1]; 
    for (j = 0 to n) dp[j][0] = dp[j][1]; 

回答はn - dp[n][0]になります。

基本的には、strからrev_strに一致する最大文字数が見つかりました。残りは追加する必要があります。こうして答えを出す。