educative.io

Count of substrings using recursion and top down approach

Courses
,
#1

How can we implement the same function using pure recursion and memoization?
We cannot simply add the nodes in the recursion tree which return 1. In doing so we would be adding some nodes multiple times due to the substructure present in the problem.

#2

Hi @Kushal, you’re right. We cannot simply add overlapping sub-problems in the recursion tree, which is why we need memoization.

Your query also seems to be already answered on another thread, where you’ll find your recursive example. You can reply to this thread if you have any further questions.

#3 
// Count of palindromic substring Top-Down DP solution
 
int findCPSRecursive(const string & st, int idx1, int idx2, vector<vector<int>> & dp) {
  if (idx1 >= idx2) {
	   return 0;
  }

  if (dp[idx1][idx2] != -1) {
	    return 0;
  }

  int c1 = 0;

  if (st[idx1] == st[idx2]) {
	if (idx2 - idx1 == 1 || idx2 - idx1 == 2) { // even & odd length check
           dp[idx1][idx2] = 1;
           return dp[idx1][idx2];
	}	
    else {
		c1 = findCPSRecursive(st, idx1 + 1, idx2 - 1, dp);
    }  
  }

  int c2 = findCPSRecursive(st, idx1 + 1, idx2, dp);
  int c3 = findCPSRecursive(st, idx1, idx2 - 1, dp);

  dp[idx1][idx2] = c1 + c2 + c3;

  return dp[idx1][idx2];	
}

class CPS {
public:
  int findCPS(const string &st) {
    
    vector<vector<int>> dp(st.length(), vector<int>(st.length(), -1));
    int count = st.length(); 
    
    return count + findCPSRecursive(st, 0, st.length() - 1, dp);
  }
};

Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: Count of Palindromic Substrings - Grokking Dynamic Programming Patterns for Coding Interviews