kavishrox's blog

Space optimization for SPOJ AIBOHP
By kavishrox, 12 years ago, In English

I was doing this particular problem 1021. Aibohphobia and not able to space optimize my DP code . Though I did it using length-lcs method , I couldn't do it this way .

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

code

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You should notice that DP state where the length(k-j+1) is L depends only on other DP states where the length is L-1 or L-2, so I think you should modify your DP state a little bit so there is length involved insted of the ending index. DP[i][j] where j is the starting point and i is the length (or vice versa) is fine. so your DP array is DP[3][6101] and DP[i%3][j]=DP[(i+1)%3][j+1] or DP[i%3][j]=min(DP[(i+2)%3][j],DP[(i+2)%3][j+1])+1 .

→ Reply