059_Longest_Reccuring_ss_DP.cpp

#include<bits/stdc++.h>
using namespace std;

class Solution {
	public:
		int LongestRepeatingSubsequence(string str){
		    int n = str.size();
		    vector<vector<int>> dp(n+1, vector<int> (n+1,0));
		    for(int i=1; i<=n; i++){
		        for(int j=1; j<=n; j++){
		            if (i == j || str[i-1] != str[j-1])
		                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		            else
		                dp[i][j] = 1 + dp[i-1][j-1];
		        }
		    }
	        return dp[n][n];
		}

};