<p>Given a string <code>s</code>, find <em>the longest palindromic <strong>subsequence</strong>&#39;s length in</em> <code>s</code>.</p>

<p>A <strong>subsequence</strong> is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bbbab&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible longest palindromic subsequence is &quot;bbbb&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbbd&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> One possible longest palindromic subsequence is &quot;bb&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists only of lowercase English letters.</li>
</ul>

class Solution {
public:
int dp[1000][1000];
    Solution(){
        memset(dp,-1,sizeof(dp));
    }
    int LCS(string text1,string text2,int m,int n){
        if(n==0||m==0){
            return 0;
        }
        if(dp[m][n]!=-1){
            return dp[m][n];
        }
        if(text1[m-1]==text2[n-1]){
            return dp[m][n]=1+LCS(text1,text2,m-1,n-1);
        }
        else{
            //either you take last character of 1st and dont take of 2nd 
            //or either you take last character of 2nd and dont take of 1st
            int a=LCS(text1,text2,m-1,n);
            int b=LCS(text1,text2,m,n-1);
            return dp[m][n]=max(a,b);
        }
    }
    int longestPalindromeSubseq(string s) {
      string s1=s;
      reverse(s.begin(),s.end());
      string s2=s;
      //return LCS(s1,s2,s.size(),s.size());
      //find the lcs of both it will be same we are reversing string 
      //lps of 1st strig will be same as lpos of second which is also lcs of both
        int n=s.size();
        int m=s.size();
       int dp[n+1][m+1];//dp meaning store lcs of strting n elements of str1 and m of str2
       for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                if(i==0||j==0){
                    dp[i][j]=0;
                }
                else if(s1[i-1]==s2[j-1]){
                    dp[i][j]=1+dp[i-1][j-1];
                }
                else{
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }
            }
       }
       return dp[n][m];
    }
};
16700