leetcode

0 class Solution {

1 int len(const string &s, const int sa, const int sb, vector<vector<int>> &mem) {

2 if (mem[sa][sb]) return mem[sa][sb];

3

4 int res = 0, a = sa, b = sb;

5 while (a < b) {

6 if (s[a] == s[b])

7 a++, b--, res += 2;

8 else {

9 res += max(len(s, a + 1, b, mem), len(s, a, b - 1, mem));

10 break;

11 }

12 }

13 if (a == b) res++;

14 mem[sa][sb] = res;

15 return res;

16 }

17

18 public:

19 int longestPalindromeSubseq(string s) {

20 int n = s.size();

21 vector<vector<int>> mem(n, vector<int>(n));

22 return len(s, 0, n - 1, mem);

23 }

24 };