<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 longestPalindromeSubseq(string s) {
        string t = s;
        reverse(s.begin(), s.end());
        return lcs(s,t);
    }
    int lcs(string s, string t)
    {
        string temp;
        if (t.length() < s.length())
        {
            // swap the strings(should simply be a re-assigning of pointers)
            temp = s;
            s = t;
            t = temp;
        }
        int s_len = s.length();
        int t_len = t.length();
        int dp[2][t_len]; 
        dp[0][0] = (s[0] == t[0]) ? 1 : 0;
        int j;
        for (j = 1; j < t_len ; j++)
        {
            dp[0][j] = (s[0] == t[j]) ? 1 : dp[0][j-1]; // Either match on your own, or ask if you've matched before
        }
        if (s_len > 1) dp[1][0] = (s[1] == t[0]) ? 1 : dp[0][0];
        for (int i = 1; i < s_len ; i++)
        {
            // cout << "Current index 'i' is " << i << endl;
            dp[1][0] = dp[0][0];
            if (s[i] == t[0])
            {
                dp[1][0] = 1;
            }
            for (j = 1; j < t_len ; j++)
            {
                // cout << "Current index 'j' is " << j << endl;
                if (s[i] == t[j])
                { // match
                    dp[1][j] = 1 + dp[0][j-1];
                    // cout << "They match! Value of f(" << i << "," << j << "): " << dp[1][j] << endl;
                }else
                {
                    dp[1][j] = max(dp[1][j-1] , dp[0][j]);
                    // cout << "They don't match! Value of f(" << i << "," << j << "): " << dp[1][j] << " Computed from f(" << i << "," << j-1 << "): " << dp[1][j-1] << " and f(" << i-1 << "," << j << "): " << dp[0][j] << endl;
                }
            }
            for (j = 0 ; j < t_len ; j++)
            {
                dp[0][j] = dp[1][j];
            }
        }
        return dp[0][t_len-1];
    }
};
7700