leetcode 516 - Longest Palindromic Subsequence

https://leetcode.com/problems/longest-palindromic-subsequence/

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
One possible longest palindromic subsequence is “bb”.

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int longestPalindromeSubseq(string s) {
int size = s.size();
int dp[size][size];

for (int len = 1; len <= size; len++) {
for (int i = 0, j = i + len - 1; j < size; i++, j++) {
if (len == 1)
dp[i][j] = 1;
else if (len == 2) {
dp[i][j] = s[i] == s[j] ? 2 : 1;
} else {
if (s[i] == s[j])
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
}

return dp[0][size-1];
}
};