这个DP程序有没有办法优化space？

Question

问题陈述：

回文是对称的字符串，即从左到右和从右到左读取的字符串相同。你要编写一个程序，给定一个字符串，确定要插入到字符串中以获得回文的最少字符数。例如，通过插入 2 个字符，字符串 "Ab3bd" 可以转换为回文（"dAb3bAd" 或 "Adb3bdA"）。但是，插入少于 2 个字符不会产生回文。

输入

第一行一个整数：输入字符串的长度N，3≤N≤5000。第二行包含一个长度为 N 的字符串。该字符串由大写字母“A”到“Z”、小写字母“a”到“z”和数字“0”到“9”组成。大写和小写字母被认为是不同的。

输出

第一行包含一个整数，这是所需的最小数字。

Link 问题 => 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;
}

我收到此代码的 "time limit exceeded"。我怎样才能解决这个问题？

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 匹配的最大字符数。剩下的将需要添加。从而给出答案。

这个DP程序有没有办法优化space？

Is there a way to optimize space in this DP program?

c++

memoization

dynamic-programming