improve memoization of lowest common substring

Revision en1, by akashtomar19, 2019-08-31 13:46:08

I was solving lowest common substring problem using memoization ,But i was unable to reduce the size of dp table,can this be done using 2d array ,here I am using 3d array.

int dp[100][100][100];
int lcsubstr(int i, int j, int s) {
    if(dp[i][j][s]!=-1)return dp[i][j][s];
	int cnt = 0;
	if (i == 0 || j == 0)return cnt;
	if (a[i - 1] == b[j - 1]) {
		cnt = max(s+1,lcsubstr(i - 1, j - 1, s + 1));
	}

	cnt = max(cnt, max(lcsubstr(i - 1, j, 0), lcsubstr(i, j - 1, 0)));
	return dp[i][j][s]=cnt;
}
Tags memoization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English akashtomar19 2019-08-31 13:46:08 579 Initial revision (published)