题目：
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1: Input:
"bbbab" Output: 4 One possible longest palindromic subsequence is "bbbb".Example 2: Input:
"cbbd" Output: 2题目分析：
1、根据题目很容易看出题目要求求出一个字符串的最长回文子序列。
2、这里最重要的一点是：求解回文子序列的过程中，如果采用两头向中间的方法，倘若两头相同，则可以直接将两头取出当作回文子序列的一部分（例如“abbaba”可以直接取出两头的‘a’，再计算“bbab”）而不用担心这样的操作会遗漏某些更优解（但不排除有别的最优解）。
3、有了2中的理论基础，利用一个函数f，参数包括字符串s以及用来指明当前要计算的字串左右下标L和R。结束条件为L == R或L + 1 == R。若没有满足结束条件，则比较字符串两头的元素s[L] == s[R]是否成立。若成立则取出再计算除去两头的字串；若不成立则分别取出左右元素计算取出后字串的结果大小，取大者作为返回值。
代码1:
int f(string &s, int locL, int locR){ //假设f(s,loc,len)表示字符串s以下标locL开始locR结尾区间最长的子序列长度。 if(locL == locR) return 1; else if(locL > locR) return 0; else{ if(s[locL] == s[locR]) return 2 + f(s, locL + 1, locR - 1); else return max(f(s, locL + 1, locR), f(s, locL, locR - 1)); } } class Solution { public: int longestPalindromeSubseq(string s) { return f(s, 0, s.size() - 1); } };4、代码1经测试算法无误。但是提交后出现超时的情况，说明算法仍然存在缺陷。仔细检查后发现：在函数f的最后一个讨论情况中，比较L+1和R-1的情况中分别可能出现L+2，L+1/R-1和L+1/R-1，R-2的子情况，如果发生就意味着L+1/R-1这种情况被计算了两次，可能会浪费大量的空间和时间，所以要避免这种重复计算的发生。
5、针对上面发现的问题，考虑每个区间段的答案采用一个二维数组保存下来。二维数字初始化为0，表示未被计算【只要经过计算则不可能为0，最少为1】，如果在计算L+1或者R-1的时候遇到对应数组元素的值不为0时，则不需要再次计算，直接取出该值。这样就避免了重复计算的情况。
6、具体的二维数组采用vector<vector<int>> m的形式来实现而不是int m[][]，因为函数并不支持引入未指明界限的二元数组。
代码2：
void f(string &s, int L, int R, vector<vector<int>> &m){ if(L == R) m[L][R] = 1; else if(L + 1 == R) m[L][R] = (s[L] == s[R]? 2 : 1); else if(s[L] == s[R]){ f(s, L + 1, R - 1, m); m[L][R] = 2 + m[L + 1][R - 1]; } else{ if(m[L + 1][R] == 0) f(s, L + 1, R, m); if(m[L][R - 1] == 0) f(s, L, R - 1, m); m[L][R] = max(m[L + 1][R], m[L][R - 1]); } } class Solution { public: int longestPalindromeSubseq(string s){ vector<vector<int>> m; for(int i = 0; i < s.size(); i++){ vector<int> temp; for(int j = 0; j < s.size(); j++) temp.push_back(0); m.push_back(temp); } f(s, 0, s.size() - 1, m); return m[0][s.size() - 1]; } };