# 516 - Longest Palindromic Subsequence

## 解法一 - 暴力法

1. 頭跟尾的字母相同：那我們就知道目前 sequence 的長度至少有 2，然後再繼續搜尋下去
2. 頭跟尾的字母不同：那就分別把頭往後移 & 尾往前移，得到兩個新的字串，然後分別搜尋

``````class Solution {
public:
int longestPalindromeSubseq(string s) {
return findLPS(s, 0, s.length()-1);
}

private:
int findLPS(string& s, int start, int end) {
if(start > end)
return 0;

// Any character is a palindrome with length 1
if(start == end)
return 1;

if(s[start] == s[end])
return 2+findLPS(s, start+1, end-1);

int l1 = findLPS(s, start+1, end);
int l2 = findLPS(s, start, end-1);
return max(l1, l2);
}
};
``````

## 解法二 - 暴力法 + Memoization

``````class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> memo(s.length(), vector<int>(s.length(), -1));
return findLPS(s, 0, s.length()-1, memo);
}

private:
int findLPS(string& s, int start, int end, vector<vector<int>>& memo) {
if(start > end)
return 0;

// Any character is a palindrome with length 1
if(start == end)
return 1;

if(memo[start][end] == -1) {
if(s[start] == s[end]) {
memo[start][end] = 2+findLPS(s, start+1, end-1, memo);
}
else{
int l1 = findLPS(s, start+1, end, memo);
int l2 = findLPS(s, start, end-1, memo);
memo[start][end] = max(l1, l2);
}
}

return memo[start][end];
}
};
``````

## 解法三 - DP

DP 解法的形式其實在上面就已經可以看出來，我們再來看一下詳細說明：

``````class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.length(), vector<int>(s.length(), 0));

// Init
for(int i=0; i<s.length(); i++)
dp[i][i] = 1;

// Build DP table
for(int start = s.length()-1; start>=0; start--) {
for(int end = start+1; end<s.length(); end++) {
if(s[start] == s[end])
dp[start][end] = 2 + dp[start+1][end-1];
else
dp[start][end] = max(dp[start+1][end], dp[start][end-1]);
}
}

return dp[0][s.length()-1];
}
};
``````