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;
}
You don't need to memorize the string for every state but only the choice that you have taken, if $$$lcsubstr(i - 1, j) > lcsubstr(i, j - 1)$$$ then it's better to skip the ith character of a, otherwise it's better to skip the jth character of b. So you can memorize your choices and then backtrack the final string.
If you want to save memory you can make choice[][] as boolean, and manually check if a[i]==b[j] and use true for skipping the ith character of a, false for skipping the jth character of b.