<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[1500][1500] = {0};
    int longestPalindromeSubseq(string s) {
        int i, j, k, len, l, r, bracket, ok;
        string ans = "", ret = "";
        for (i=0; i<s.size(); i++){
            dp[i][i]=1;
        }
        for (i=1; i<s.size(); i++){
            dp[i-1][i]=1+(s[i-1]==s[i]);
        }
        for (i=2; i<s.size(); i++){
            for (j=0; (j+i)<s.size(); j++){
                //j = start
                //i+1 = length (e.g. 0->2, i=2 but length is 3)
                k = j+i; //j is end, inclusive
                dp[j][k] = (s[j]==s[k])*2 + dp[j+1][k-1];
                //cout<<j<<" "<<k<<" "<<dp[j][k]<<"\n";
                dp[j][k] = max(dp[j][k], dp[j+1][k]);
                //cout<<j<<" "<<k<<" "<<dp[j][k]<<"\n";
                dp[j][k] = max(dp[j][k], dp[j][k-1]);
                //cout<<j<<" "<<k<<" "<<dp[j][k]<<"\n";
            }
        }
        /*
        cout<<"ans "<<dp[0][s.size()-1]<<"\n";;
        len = dp[0][s.size()-1];

        l = 0;
        r = s.size()-1;
        while (l < r){
            ok = 0;
            bracket = r - l; //exactly 1 smaller than l..r inclusive
            cout<<"l "<<l<<" r "<<r<<" bracket "<<bracket<<"\n";
            for (i=l; i+bracket-1<=r; i++){
                cout<<"check "<<i<<" "<<(i+bracket-1)<<" "<<dp[i][i+bracket-1]<<"\n";
                if (dp[i][i+bracket-1] == len){
                    l = i;
                    r = i+bracket-1;
                    bracket--;
                    ok = 1;
                    break;
                }
            }
            if (!ok){
                ret += s[l];
                cout<<"add "<<s[l]<<" "<<s[r]<<"\n";
                len -= 2;
                l++;
                r--;
            }
        }
        //bracket is supposed to be 0 now
        ans = ret;
        reverse(ret.begin(), ret.end());
        if (len){
            ans += s[l];
        }
        ans += ret;
        */
        
        return dp[0][s.size()-1];

    }
};
17800