<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:
    vector<vector<int>> dp;
    //dp[i][j] : lens of subsequence
    int f(int i,int j,string& s)
    {
        if(i == j)//only one char
            return 1;
        else if(j - i == 1) // two char
            return ((s[i] == s[j]) ? 2 : 1);
        else if(dp[i][j] != -1)
            return dp[i][j];
        
        else 
        {
            int mx = -1;// more than two
            mx = f(i+1,j-1,s) + 2 * (s[i] == s[j]);
            mx = max(mx,max(f(i+1,j,s),f(i,j-1,s)));
            return dp[i][j] = mx;
        }
    }
    int longestPalindromeSubseq(string s) {
        int len = s.size();
        dp.resize(len);
        for(int i = 0;i < len;i++)
        {
            dp[i].resize(len);
            for(int j = 0;j < len;j++)
                dp[i][j] = -1;
        }
        int max_len = 1;
        for(int i = 0;i < len;i++)
        {
            for(int j = i;j < len;j++)
            {
                max_len = max(max_len,f(i,j,s));
            }
        }
        return max_len;
    }
};
74500