akashtomar19's blog

By akashtomar19, history, 5 years ago, In English

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;
}

Full text and comments »

  • Vote: I like it
  • -9
  • Vote: I do not like it